How to solve any Dynamic Programming Question?

So, let’s start with a quote from Confucius.

“Study the past if you would define the future.” - Confucius

The quote let’s us know all we need to know about dynamic programming. We need to remember the results computed for previous small problems to solve bigger newer problems.

There are 2 approaches to dynamic programing usually

• Tabulation - Bottom Up
• Memoization - Top Down

We can take a common problem “Fibonacci Series” to understand the approaches.

The first thing we can try to do is solve it by recursion. So, the recursion solution for Fibonacci is as follows

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

If we consider the above solution and compute the recursion tree we get the following tree for n = 5.

1. fib(5) => 5
   1. fib(4) => 3
      1. fib(3) => 2
         1. fib(2) => 1
            1. fib(1) => 1
            2. fib(0) => 0
         2. fib(1) => 1
      2. fib(2) => 1
         1. fib(1) => 1
         2. fib(0) => 0
   2. fib(3) => 2
      1. fib(2) => 1
         1. fib(1) => 1
         2. fib(0) => 0
      2. fib(1) => 1

Memoization

#

As we can see above, we have overlapping sub problems, so we don’t need to solve these problems again and again. We can store these solutions, this is memoization. We have a single parameter, so we would need a 1D array.

So how do we apply memoization. We do it with 3 steps.

1. Declare the DP array.
2. Start adding the solution for computed sub problems into DP array.
3. Check if the solutions already exists and use it if it exists.

int fibonacci(int n, int[] dp/* Adding the DP array*/){
    if (n <= 1) return n;
    if (dp[n] != -1) return dp[n]; //Checking if solution exists and using it
    dp[n] = fibonacci(n - 1, dp) + fibonacci(n - 2, dp);//Updating the array if it doesn't exist
    return dp[n];
}

So, the time complexity would be O(n). This is because we don’t call the function again for already computed solutions. But, the space complexity would be O(n) + O(n), one for the dp array and another for the extra stack space.

Tabulation

#

So, now let’s try tabulation. As already highlighed above this is a bottom up approach. For the current problem, let’s try to rewrite it with tabulation.

int fibonacci(int n){
    int[] dp = new int[n + 1];
    Arrays.fill(dp, -1);
    dp[0] = 0; 
    dp[1] = 1;
    for(int i = 2; i <= n; i++){
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

We calculated the base cases first and start iterating and solving the bigger solutions with previous computed values.

The time complexity is the same, i.e. O(n). The space complexity comes down here because we are not using the stack trace which is O(n).

Space optimisation on Tabulation

#

In the above tabulation, we can see that we don’t need to maintain all the previous values. Just the last two solutions would suffice for this problem.

int fibonacci(int n){
    int a = 0, b = 1;
    for(int i = 2; i <= n; i++){
        int cur = a + b;
        a = b;
        b = cur;
    }
    return b; //since computing till n 
}

So, now we have reduced the space complexity to O(1), while the time complexity stays the same.

Now, we will move on to some more complex problem to apply the above approach in the coming articles.