Dynamic Programming in a New Avatar: Part 1

Introduction

In this post, we learn about concepts and tricks of dynamic programming. This article helps you learn ways of “how to think” when you get a DP problem.

5 Steps to solve a DP problem

1. Define Sub-problems – Break down the problem into subproblems. Each subproblem should be a same as the actual problem.
2. Guess (Draw a solution to a subproblem) – Now you know subproblems, try to solve the subproblem which is actually a smaller version of the actual problem. Also, try to find the base cases in this step.
3. Recurrence – Now you know sub-problems and the actual problem. Try to relate them. Generate a recurrence equation that establishes a relation with the subproblems with the actual problem.
   
   Time complexity = Number of sub-problems * (Time taken to solve each sub-problem)
   
   
4. Recurse / Memoize (or Bottoms-Up Approach) – We broke the actual problem into sub-problem so that we could know the result of the sub-problem and re-use it every time we need it. So, we need to store the solved answer of the sub-problem (called memoization) and use it when needed.
   For Bottoms-Up Approach, you need to determine if the recurrence is a DAG (Directed-Acyclic-Graph), meaning is there a topological sorting that can be done in all sub-problems which can lead up to the actual problem. This is important for Bottoms-Up approach and then only you can write iterative version (for-loop) solution of the problem.
5. Solve the Original Problem – This means now that you have solved each sub-problem, you have to solve the original problem, by using a set of sub-problem solutions or usually a subproblem itself.

How to define sub-problems for String or Sequence DP questions?

In this section, we will learn how to perform first step (of 5 defined above) for string DP or sequence DP questions.

Sub-problems for String / Sequence DP

• Suffixes – [ i : ] ∀ i – solving for a suffix can be a possible sub-problem. # of subproblems – O(n)
• Prefixes – [ : i ] ∀ i – solving for a prefix can be a possible sub-problem. # of subproblems – O(n)
• Substrings – [ i : j ] ∀ ( i, j )] – solving for a substring can be a possible sub-problem. # of subproblems – O(n²)

Let’s solve some problems with above concept.

Problem 1 : Partition Equal Subset Sum (Leetcode) – Link
Given an integer array ‘a‘, return ‘true’ if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or ‘false’ otherwise.

Solution 1 : Correct but gives Memory Limit Exceeded due to 3D Array.

1. Sub-problems
   • Suffixes [ i : ]
   • Number of sub-problems = O(n)
     
2. Guess for each sub-problem
   • If at i, should i put it in subset 1 or subset 2.
   • You would also need sum in subset 1 (S1) and subset 2 (S2).
   • Time to solve subproblem iterate through all possible pairs of (S1, S2).
     
3. Recurrence
   • DP(i, S1, S2) = max { DP (i+1, S1+a[i], S2), DP (i+1, S1, S2+a[i]) }
   • Time complexity = O(n)
     
4. Topological sort
   • Each state in recursion can be represented as a D.A.G (Directed Acyclic Graph). This means that we can follow the bottoms-up approach.
     
5. return DP(0, 0, 0)

boolean canPartition(int[] a){
  for(i = n-1 to i): // n is the length of array
    for(s1 = W to 0):  
      for( s2 = W-a[i] to 0):
        DP[i][s1][s2] = Math.max(DP[i][s1+a[i]][s2], DP[i][s1][s2+a[i]])
  
  return DP[0][0][0] == 1
}

Solution 2 : Accepted

Notice in step 2

2. Guess for each sub-problem
We say we need subsets as well S1, S2. But if you observe, you only need one subset S1, because
S2 = Prefix[i] – S1 because Whatever is S1, S2 is the remaining only (as there are 2 subsets only).

3. Recurrence

• DP(i, S1, S2) = max { DP (i+1, S1+a[i], S2), DP (i+1, S1, S2+a[i]) }
• Time complexity = O(n)

boolean canPartition(int[] a){
    int n = a.length;
    
    // Get the sum of the array to check if it is possible to 
    // divide the array into subsets of equal sums.
    
    int sum = 0;
    for(int i = 0; i < n; i++)
        sum += a[i];
        
    // if the sum itself is odd, the array can't be divided into
    // equal sums
    if(sum % 2 != 0) return false;
    
    // W is the value that each equal subset will sum up to.
    int W = sum / 2;
    
    // Obtain the prefix array.
    int[] prefix = new int[n+1];
    prefix[1] = a[0];
    for(int i = 2; i <= n; i++){
        prefix[i] = prefix[i-1] + a[i-1];
    }
    
    // Create a 2-D array.
    int[][] DP = new int[n+1][sum+1];
    // Define the end-state.
    DP[n][W] = 1;
    
    // DAG Iteration.
    for(int i = n-1; i >= 0; i--){
        for(int s1 = W-a[i]; s1 >=0; s1--){
            if(pr[i] >= s1)
                DP[i][s1] = Math.max(DP[i+1][s1+a[i]], DP[i+1][pr[i]-s1]);
        }
    }
    
    return DP[0][0] == 1;
}

See you in next one !