Dynamic Programming Guide

Using Dynamic Programming for Problem Solving

Dynamic Programming (DP) is a bottom-up approach to problem solving where one sub-problem is solved only once. In many cases DP requires a different view to the problem and is often counter-intuitive, leaving beginners to the topic feeling overwhelmed.

This article reviews the basic steps and promotes understanding the approach and emphasizes problem solving by breaking it down as steps to be followed.

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:

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:

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:


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