Using Dynamic Programming for Problem Solving

Returning to Problem Solving Fundamentals

Before discussing Dynamic programming approaches let's first revisit the fundamental roots of the problem solving process. Essentially, we can break problem solving down into four main steps:

1. First you need to understand the problem at hand. Until you understand the problem and are able to convey it to someone else, don't move forward!
2. After understanding, make a plan. Often times when solving real world problems you'll find that plans are useless but planning is indispensable.
3. Carry out the plan! This step requires patience but you should persist. If you find the plan continuing to fail, revisit previous steps.
4. Look back on your work. Think about how you could make it better. Can you extend your work? Most importantly, revisit your work to conclude any lessons learned that you may carry with you to new situations.

Further, if these steps fail you should try to understand and solve a simpler version of the problem or even a problem that is related. We should always carry out these steps, even if they're not explicitly written out.

Determining if Dynamic Programming is Appropriate

While we may be tempted to dive right into different techniques, we should first understand how each technique works and when it is applicable.

When it comes to Dynamic programming, perhaps the best check is to investigate for optimal substructure and overlapping sub-problems. Dynamic programming can be applied when there is a complex problem that is able to be divided into sub-problems of the same type and these sub-problems overlap, be it completely or partially.

The most obvious example of overlapping sub-problems is computing the Fibonacci numbers.

fibonacci(n) = fibonacci(n-1) + fibonacci(n-2) ##for n > 1

It is most often the case that Dynamic programming is considered when we are trying to solve an optimization problem (e.g., maximizing, minimizing, or finding the total number of possible ways to do something) and the optimal solution for larger parameters relies on optimal solutions of the same problem structure with smaller parameters.

Dynamic programming is excellent for solving complex problems that have the property of overlapping sub-problems and optimal substructures

We can determine if a problem is suitable for Dynamic programming by answering the follow questions:

1. Can we divide the problem into sub-problems of the same structure?
2. Do the sub-problems overlap?
3. Is this an optimization problem?

Typically we only need to answer "yes" to the first two questions to have a high chance that Dynamic programming will get the job done.

Solving Dynamic Programming Problems

While there is no recipe for solving all Dynamic programming problems, we can use the following steps to solve most standard Dynamic programming problems:

1. Determine if Dynamic programming is appropriate. This relates back to the previous section.
2. Define the problem recursively. Having sub-problems of the same type naturally leads to recursive solutions. (This topic alone could have it's own article.)
3. Attempt memoization if applicable. Memoization is just the mathematical/computing term for caching values. Essentially we would like to have a simple lookup table for when the same sub-problem is encountered multiple times.
4. Attempt solving Bottom-up. This is perhaps the most difficult step that requires the most practice. The goal of this step is to eliminate recursion and redefine your solution in a forward manner, starting from the most basic case. The goal of this is to only cache the results that are required to solve the larger problem.

Notice that steps 2, 3, and 4 are all improvements of each other. It is typical for beginners to stop at step 3 although you'll see improvement to solution speed by moving to step 4.

Applications of Dynamic Programming

1. 0/1 knapsack problem
2. Mathematical optimization problems
3. All pairs shortest path problem
4. Reliability design problem
5. Longest common sub-sequence (LCS)
6. Flight and robotics controls
7. Time-sharing: scheduling jobs to maximize CPU usage