Dynamic Programming

Dynamic programming, often abbreviated “DP”, is a technique to efficiently solve recursion problems – problems whose solutions depend on solutions of smaller subproblems – by storing partial results. Many times, it is obvious that a given problem is a recursion problem. However, it may not be so obvious that using DP will tremendously speed up the solution. When have read the description of a problem and started to solve it, first look at its restrictions. If a polynomial-time algorithm should be developed, then it's possible that the solution may be of DP type. In this case try to see if there exist such states (sub-solutions) with the help of which the next states (sub-solutions) may be found. Having found that - think about how to pass from one state to another. If it seems to be a DP problem, but you can't define such states, then try to reduce the problem to something you already know how to do.

## Techniques of Dynamic Programming

There are two main types of Dynamic Programming.
Top-down approach: The problem is broken into subproblems, and these subproblems are solved and the solutions remembered, in case they need to be solved again. This is recursion and memoization combined together.
Bottom-up approach: All subproblems that might be needed are solved in advance and then used to build up solutions to larger problems. This approach is slightly better in stack space and number of function calls, but it is sometimes not intuitive to figure out all the subproblems needed for solving the given problem.

An example of this would be computing the fifth Fibonacci number. A top-down approach would look like this:
1. fib(5)
2. fib(4) + fib(3)
3. (fib(3) + fib(2)) + (fib(2) + fib(1))
4. ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
5. (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

The top-down approach must call several subproblems for each subproblem, which leads to an exponential time. In the bottom-up approach we calculate the smaller values of fib first, then build larger values from them. This method uses linear (O(n)) time since it contains a loop that repeats n − 1 times. Normal humans would mentally calculate Fibonacci with this bottom-up approach.

## The Grand Scheme

Although useful for explaining the basic function of DP, Fibonacci's sequence doesn't cover all of what DP can do. One-dimensional DP is clear and can be used to build things up directly on each other, but there is also the case of two-dimensional DP which can be quite useful. Problems just as coins on the grader and money on the 2007 Gold Qualifying Round for USACO illustrate the need for more complex DP.

## Vocabulary

State(subproblem)- A simpler part of a large problem that can be broken up into states which are easier to work with.
Recursion-problems whose solutions depend on solutions to smaller subproblems

## Sample Problem Area

How does this sound wikifolk?

page revision: 3, last edited: 12 Nov 2007 06:56