Dp Series Java - Dynamic Programming an Introduction

In this article, we will be going to understand the concept of dynamic programming.

Dynamic Programming can be described as storing answers to various sub-problems to be used later whenever required to solve the main problem.

The two common dynamic programming approaches are:

Memoization: Known as the “top-down” dynamic programming, usually the problem is solved in the direction of the main problem to the base cases.
Tabulation: Known as the “bottom-up ” dynamic programming, usually the problem is solved in the direction of solving the base cases to the main problem

The below image gives the understanding of the above concepts.

We will be deep diving into these concepts using a familiar problem statement which is Fibonacci numbers.

The example is as follows:

0,1,1,2,3,5,8,13,21,…

where i = (i-2) + (i-1) can be written in function as f(n) = f(n-2) + f(n-1)

Solution :

Part – 1: Memoizaton

If we draw the recursive tree for n=5, it will be:

Steps to memoize a recursive solution:

Any recursive solution to a problem can be memoized using these three steps:

Create a dp[n+1] array initialized to -1.
Whenever we want to find the answer of a particular value (say n), we first check whether the answer is already calculated using the dp array(i.e dp[n]!= -1 ). If yes, simply return the value from the dp array.
If not, then we are finding the answer for the given value for the first time, we will use the recursive relation as usual but before returning from the function, we will set dp[n] to the solution we get.

Now, following the recursive code we see that at n=5, the value of dp[5] is equal to -1 therefore we need to compute its value and go to the inner recursive calls. Similar is the case at n=4, n=3, and n=2. For n=2, we hit our two base conditions as the inner recursive calls.

As we traverse back after solving n=2, we update its dp array value to 1 ( the answer we got). Similarly, for the second recursive call for n=3, we again hit a base condition and we get an answer of f(n=3) as 2, we again update the dp array.

Then for the second recursive call f(n=4), we see that dp[2] is not equal to -1, which means that we have already solved this subproblem and we simply return the value at dp[2] as our answer. Hence we get the answer of f(n=4) as 3(2+1).

Similarly, for the second recursive call f(n=5), we get dp[3] as 2. Then we compute for(n=5) as 5(2+3).

import java.util.*;
class Fibo{
    public static void main(String args[]) {

      int n=5;
      int dp[]=new int[n+1];
      Arrays.fill(dp,-1);
      System.out.println(f(n,dp));

    }
    static int f(int n, int[] dp){
    if(n<=1) return n;

    if(dp[n]!= -1) return dp[n];
    return dp[n]= f(n-1,dp) + f(n-2,dp);
    }
}

//Output: 5
//Time Complexity: O(N)
//Space Complexity: O(N)

Part -2: Tabulation

Tabulation is a ‘bottom-up’ approach where we start from the base case and reach the final answer that we want.

Steps to convert Recursive Solution to Tabulation one.

Declare a dp[] array of size n+1.
First initialize the base condition values, i.e i=0 and i=1 of the dp array as 0 and 1 respectively.
Set an iterative loop that traverses the array( from index 2 to n) and for every index set its value as dp[i-1] + dp[i-2].

import java.util.*;
class Fibo{
    public static void main(String args[]) {

      int n=5;
      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];
      }
      System.out.println(dp[n]);
    }
}

//Output: 5
//Time Complexity: O(N)
//Space Complexity: O(N)

Part 3: Space Optimization

If we closely look at the relation,

dp[i] = dp[i-1] + dp[i-2]

we see that for any i, we do need only the last two values in the array. So is there a need to maintain a whole array for it?

The answer is ‘No’. Let us call dp[i-1] as prev and dp[i-2] as prev2.

Each iteration’s cur_i and prev become the next iteration’s prev and prev2 respectively.
Therefore after calculating cur_i, if we update prev and prev2 according to the next step, we will always get the answer.
After the iterative loop has ended we can simply return prev as our answer.

import java.util.*;
public class Fibo{
    public static void main(String args[]) {
        int n=5;

        int prev2 = 0;
        int prev = 1;

        for(int i=2; i<=n; i++){
            int cur_i = prev2+ prev;
            prev2 = prev;
            prev= cur_i;
        }
        System.out.println(prev);
    }
}

//Output: 5
//Time Complexity: O(N)
//Space Complexity: O(1)

Social Links:

Twitter

Github