Dynamic Programing Simplified

Dynamic programing has been infamous for being counterintuitive. Here we will dig into series of approaches that help intuitively solve many problems.

The technique is called :

Inclusion Exclusion principle ( I just made that up :P. Its actually backtracking)

Anyways, as the name suggests, it involves either include an item or exclude an item. It’s that simple.

Let’s solve a bunch of problems to understand the above principle. Our approach will be to first solve with intuition. Then make it a bit faster.

Problems discussed

Problem 1: Coin Change — LeetCode

Problem 2: Jump Game — LeetCode

Problem 3: Climbing Stairs — LeetCode

Problem 4: Longest Common Subsequence — LeetCode

Problem 5: House Robber — LeetCode

Problem 6: Interleaving Strings

Problem 1: Coin Change — LeetCode

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

To get 11 :

Take 1 — the problem becomes : coins = [1,2,5], amount = 11–1 = 10

Don’t take 1 — the problem becomes : coins = [2,5], amount = 11

To arrive at solution we will recursively call the same problem with reduced amount or the reduced coin set

for(int n: coins){
            int include=0;
            if(n<=amount) {
                //Include coin n, 
                //call problem recursively with amount -n
                 //Add 1 since we collected 1 coin
               include = 1+coinChange(coins,amount-n ); 
            }
          //If we are not including means its excluded 
           min = include>0 ? Math.min(min,include) : min;
}

Full code with memoization

HashMap<Integer,Integer> memo= new HashMap<>();
    public int coinChange(int[] coins, int amount) {
        if(memo.containsKey(amount)) return memo.get(amount);
        if(amount == 0) return 0;
        if(amount <0) return -1;//we took a bigger coin
        int min = Integer.MAX_VALUE;

        for(int n: coins){
            int include=0;
            if(n<=amount) {
                include = 1+coinChange(coins,amount-n ); 
            }
            min = include>0 ? Math.min(min,include) : min;
        }
        int ans = min==Integer.MAX_VALUE ? -1 : min;
        memo.put(amount,ans);
        return ans;
    
    }

Problem 2: Jump Game — LeetCode

Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Include the nums[i] : then jump to index ranging from 1 to i+nums[i]

Either include the jump in answer or dont include.

After jumping to an index, recursively call the same problem with updated index.

        for( int j =1;j<=nums[start];j++){ //jump in range
            int jump = start+j;
            if(jump<nums.length){
                boolean ans = jump(nums,start+j);
                if(ans) return true;
            }
           //no else condition means that you didnot  jump
        }

Full code with memoization

class Solution {
    int[]memo;
    public boolean canJump(int[] nums) {
        memo = new int[nums.length];
        //Start with index 0
        return jump(nums,0);
    }
    
    private boolean jump(int[]nums, int start){
        if(memo[start]==1 || start>=nums.length)return false;
        
        //If end reached
        if(start ==nums.length-1)return true; 
       
       //Jump in range from start to start+j;
        for( int j =1;j<=nums[start];j++){
            int jump = start+j;
            if(jump<nums.length){
                boolean ans = jump(nums,start+j);
                if(ans) return true;
            }
            memo[jump]=1; // this j didnot result in reaching end
        }    
        return false;
    }
}

Problem 3: Climbing Stairs — LeetCode

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Did you notice the similarity with coin change problem

Include 2 steps : recursively call from current+2 step, else call with current91 step

We need to track what step you are at ( current).

Memo will store previously stored answer when you are at step current.

class Solution {
    HashMap<Integer, Integer> memo;
    public int climbStairs(int n) {
        memo = new HashMap<>();
        return climb(0,n);
    }
    
    private int climb(int current, int n){
        if(current==n) return 1;
        if(memo.containsKey(current)) return memo.get(current);
        //Climb 2 steps if you dont overflow
        int twoSteps = current+2<=n  ? climb(current+2,n) : 0;
        //Number of ways after climbing 1 step 
        int totalSteps = climb(current+1,n) +  twoSteps;
        memo.put(current,totalSteps);
        return totalSteps;
    }
}

Problem 4: Longest Common Subsequence — LeetCode

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

If characters are same, include else exclude. Recurse with subproblem

if(s.charAt(i)==t.charAt(j)) including = 1+lcs(s,t,i+1,j+1);
int excluding = Math.max(lcs(s,t,i+1,j),lcs(s,t,i,j+1));
int ans = Math.max(including,excluding);

To memoize, store ans for the state i,j

int[][] map;
    public int longestCommonSubsequence(String s, String t) {
        map = new int[s.length()][t.length()];
        return lcs(s,t,0,0);
    }
    
    private int lcs(String s, String t, int i, int j){
        if(i==s.length() || j==t.length()) return 0;
        if(map[i][j]!=0) return map[i][j];
        int including =0;
        if(s.charAt(i)==t.charAt(j)) including = 1+lcs(s,t,i+1,j+1);
        int excluding = Math.max(lcs(s,t,i+1,j),lcs(s,t,i,j+1));
        int ans = Math.max(including,excluding);
        map[i][j]=ans;
        return ans;
    }

Problem 5: House Robber — LeetCode

The robber can only chose alternative houses. Find the combination of houses that maxes sum.

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

If you chose house 1 then sub problem = [3,1], amount with robber = 1

if you dont chose house 1 then sub problem = [2,3,1], amount with robber = 0

int including = 0,excluding = 0;
        if(prev==false) {
            including = nums[i] + robHouse(nums,true,i+1);
        }
 excluding = robHouse(nums,false,i+1);
 int ans = Math.max(including,excluding);

Why the variable prev : to keep track if previous index was picked or not.

Remember we need to only pick alternative house

To memoize, store whats max with previous index included, and whats max with it excluded

class Solution {
    HashMap<Integer,Integer> prevIncluded;
    HashMap<Integer,Integer> prevExcluded;
    public int rob(int[] nums) {
        prevIncluded = new HashMap<>();
        prevExcluded = new HashMap<>();
        //Start with house 0
        return robHouse(nums,false,0);
    }
    private int robHouse(int[] nums, boolean prev,int i){
        if(i==nums.length)return 0;
        //Memoization
        if(prev && prevIncluded.containsKey(i)){
            return prevIncluded.get(i);
        }else if(!prev && prevExcluded.containsKey(i)){
            return prevExcluded.get(i);
        }
                 
        int including = 0,excluding = 0;
        if(prev==false) {
            including = nums[i] + robHouse(nums,true,i+1);
        }
        excluding = robHouse(nums,false,i+1);
        int ans = Math.max(including,excluding);
        //Saving memoization
        if(prev){
            prevIncluded.put(i,ans);
        }else{
            prevExcluded.put(i,ans);
        }
        return ans;
        
    }
}

Problem 6: Interleaving Strings

A thing to note is that if characters match, it could have come from s1 or s2.

Terminating condition is when we have traversed s1,s2 & s3.

boolean dp(int p1, int p2, int p3){
        //Terminating condition
        if(p3==s3.length()) return p2==s2.length() && p1==s1.length();
        //match and proceed
        boolean includingCharFromS1 = (p1<s1.length()) && (s1.charAt(p1)==s3.charAt(p3) && dp(p1+1,p2,p3+1));
        boolean includingCharFromS2 = (p2<s2.length()) && (s2.charAt(p2)==s3.charAt(p3) && dp(p1,p2+1,p3+1));
        //Either interleaving should be true
        return includingCharFromS1 || includingCharFromS2;
    }

Memoize position of pointers and value of interleaving

boolean dp(int p1, int p2, int p3){
        Pair<Integer,Integer> pos = new Pair(p1,p2);
        if(memo.containsKey(pos)) return memo.get(pos);
        //Terminating condition
        if(p3==s3.length()) return p2==s2.length() && p1==s1.length();
        //match and proceed
        boolean includingCharFromS1 = (p1<s1.length()) && (s1.charAt(p1)==s3.charAt(p3) && dp(p1+1,p2,p3+1));
        boolean includingCharFromS2 = (p2<s2.length()) && (s2.charAt(p2)==s3.charAt(p3) && dp(p1,p2+1,p3+1));
        
        memo.put(pos,includingCharFromS1 || includingCharFromS2);
        //Either interleaving should be true
        return memo.get(pos);
    }