Dynamic Programming
From VT.Prog
Dynamic Programming (DP) means different thing to different people. You'll find all sorts of odd descriptions in various texts.
For our purposes, DP means breaking down a problem to a minimal amount of state information, grouping equivelent states together and solving a problem in segments.
This can often turn a problem that has 20 steps, with 10 options on each step (10 ^ 20 operations) to a problem with a limited number of cases for each step (100 * 20 operations).
Contents |
Examples
Greater NY 2002 - E - Unimodal Palindromic Decompositions
Note, the DP solution is a bit slow on 2007 computers. Most likely there is a faster solution that would have run nicely on the slightly slower systems of 2002. However, it is a fairly easy to understand DP problem.
The basic idea here is:
- Figure out the minimum possible state information that we care about.
- For this problem, it works out to a sum of numbers and a highest number.
- so the state expresses { <who cares> H ... H <who cares> } where H is our highest number and the sum is the sum of both H's and both <who cares> blocks and the ... is yet to be determined.
- This means that {1 1 2 ... 2 1 1} is the same as {2 2 ... 2 2}. They both sum to 8 and have the highest number 2. Meaning that anything else in the middle has to be at least 2. This is all we need to know.
- So now we can use a map that maps states to number of ways to reach that state. That is the map<State,long long>.
- Write a function that takes a list of those states, adds elements to it to create new states.
Greater NY 2006 - I - Margaritas on the River Walk
This is very similar to the other, in that you are counting the number of ways to do something.
