Dynamic Programming

Dynamic programming (or simply DP) is a method of solving a problem by solving its smaller subproblems first. Often, it's one of the hardest algorithm topics for people to understand, but once you learn it, you will be able to solve a wide range of problems with it.

Simple dynamic programming

We can see a simple way to use dynamic programming by calculating Fibonacci numbers. We know that F₀ = 0, F₁ = 1, and F_n = F_n-1 + F_n-2. Here is how you would calculate Nth Fibonacci number without dynamic programming:

int fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    
    int f1 = 0, f2 = 1;
    for (int i = 2; i <= n; i++) {
        int next = f1 + f2;
        f1 = f2;
        f2 = next;
    }

    return f2;
}

System.out.println(fibonacci(7));  // 13
System.out.println(fibonacci(12)); // 144

And here is how we can calculate first N Fibonacci numbers with dynamic programming. You can see that the code here is really simple, and it follows Fibonacci numbers definition in a very straightforward manner:

final int N = 15;
int[] f = new int[N];

f[0] = 0; f[1] = 1;
for (int i = 2; i < N; i++)
    f[i] = f[i - 1] + f[i - 2];

// [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
System.out.println(Arrays.toString(f));

So, where is dynamic programming here? You can see that to calculate Nth Fibonacci number, we need N-1th and N-2th numbers – smaller subproblems that we have already solved and stored in the array f. Likewise, in other dynamic programming problems we solve smaller subproblems first, and store their result to calculate bigger subproblems with their help later.

Dynamic programming problems

Alright, let's solve some dynamic programming problems to practice with them. Try the following problem, and then see its solution to learn more:

The following problem is very similar to the previous one, but solves a slightly different question. Can you solve it?

2D dynamic programming

With 2D dynamic programming, we have more than one dimension to our problem. Try to solve the following problem to learn more:

The following problem is also similar to the previous one, but again asks a different question. Can you solve it?

Longest Increasing Subsequence

Let's solve one of the classic dynamic programming problems: longest increasing subsequence.

Knapsack-like problems

In the following problems, you need to find the number of ways or the minimum cost to accumulate some amount – very similar to the classic Knapsack problem. Try to solve the problems to learn more about it:

In the following problem, you are counting a number of ways to reach some amount:

Can you try to solve the following problem with the similar dynamic programming?

Memoization

Sometimes, finding the right order in which to calculate the dynamic programming subproblems is quite tricky. In cases like this, you can use memoization: simply calculate them in any order you like, but make sure to never solve the same subproblem twice. Usually, this is done with recursion.

For example, we could calculate the Fibonacci numbers in the following manner. This does the job, but it's inefficient, because it does the same calculation many times:

int fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    
    return fibonacci(n - 1) + fibonacci(n - 2);
}

System.out.println(fibonacci(7));  // 13
System.out.println(fibonacci(12)); // 144

We can use an array to keep track of the values we have already calculated. In the next example, f[x] is null if we didn't yet calculate the x-th Fibonacci number, and the number itself otherwise. This way, we calculate each Fibonacci number maximum once. See the code for the details:

int fibonacci(int n, Integer[] f) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    
    if (f[n] != null)
        return f[n];
    
    f[n] = fibonacci(n - 1, f) + fibonacci(n - 2, f);
    return f[n];
}

final int N = 30;
Integer[] f = new Integer[N];

System.out.println(fibonacci(7, f));  // 13
System.out.println(fibonacci(12, f)); // 144

In the code above, array f was used for the memoization of the states that are already calculated. Note how the code didn't change much, except storing the results in the array. Also note how we simply call fibonacci(7, f) to get the 7th number, and don't care which other numbers we have already calculated before.

Memoization comes handy in the following problem. Try solving it:

More dynamic programming problems

Learning dynamic programming is pretty hard, and the best way is probably to try solving more problems and reading their solutions. Here is a list of more good dynamic programming problems: