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 subproblems, 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 highlighted 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 started iterating and solving the bigger solutions with previously 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 optimization 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 problems to apply the above approach in the coming articles.