# Editing Dynamic programming

**Warning:** You are not logged in. Your IP address will be publicly visible if you make any edits. If you **log in** or **create an account**, your edits will be attributed to your username, along with other benefits.

The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.

Latest revision | Your text | ||

Line 132: | Line 132: | ||

So we can finally conclude that the total number of ways to go from <math>x_0</math> to <math>x_n</math> is the ''sum'' of the number of ways to go from <math>x_0</math> to <math>x_i</math> for all <math>i</math> such that we can make the trip from <math>x_i</math> to <math>x_n</math> in a single step (that is, <math>A \leq x_n - x_i \leq B</math>). | So we can finally conclude that the total number of ways to go from <math>x_0</math> to <math>x_n</math> is the ''sum'' of the number of ways to go from <math>x_0</math> to <math>x_i</math> for all <math>i</math> such that we can make the trip from <math>x_i</math> to <math>x_n</math> in a single step (that is, <math>A \leq x_n - x_i \leq B</math>). | ||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

===Pseudocode implementation=== | ===Pseudocode implementation=== | ||

Line 155: | Line 148: | ||

</pre> | </pre> | ||

− | + | <!-- | |

− | + | ==General example: Nukit== | |

− | + | The problem {{Problem|ccc08s5|Nukit}} | |

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | == | + | |

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | === | |

− | + | ||

− | + | ||

− | |||

− | |||

− | + | ==Counting example: Water Park== | |

+ | Another problem that admits a simple dynamic solution is {{Problem|ccc07s4|Water Park}}. The input is a network of water slides. Each water slide connects two points, and you always slide from the higher point to the lowest point, for obvious reasons, but there may be multiple water slides that go into or come out of a single point. The problem is to determine how many different ways there are to go from the highest point (labelled 1) to the lowest point (labelled <math>n</math>) by sliding down the given water slides. Two ways are different if at one of them uses a slide that the other one does not use. | ||

− | + | This problem may be abstracted as follows: you are given a [[directed acyclic graph]]. The network of water slides is a graph, where each point is a vertex and each slide is an edge; it is directed because you can only go one way along each edge; and it is acyclic because you cannot proceed down a sequence of slides and get back to where you started from (you will always end up somewhere lower). You want to determine how many different paths there are in this graph between a given pair of nodes. | |

+ | --> | ||

[[Category:Algorithms]] | [[Category:Algorithms]] |