Thursday, October 9, 2014

Nine Chapter: Lesson 5: Dynamic Programming

Outline:
A. Four steps to solve DP problems:

  1. Define DP array, 1D, 2D or even 3D. Figure out the meaning of each element in the DP array
  2. Transit function
    1. Figure out the connections between each state, how to deduce current status from the past status
  3. Initialization
    1. Figure out what is the starting status 
  4. Return answer
    1. Figure out the final status
B. How to determine if a question is a DP problem:
There are some common rules to follow:
  • Maximum/Minimum
  • Yes/No
  • Count all possible solutions
  • Cannot sort/swap
C. Four most common types of DP questions
  1. Matrix DP
  2. Sequence DP
  3. Two sequence DP
  4. Backpack

I. Matrix DP
  • dp[x][y] means from starting point to index x, y
  • Transit function: Analyze how to deduce dp[i][j] from previous states
  • Initial state:  Starting point
  • Final state:   Final point
1. Unique Path II

Follow up for "Unique Paths":
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as 1 and 0 respectively in the grid.
For example,
There is one obstacle in the middle of a 3x3 grid as illustrated below.
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
The total number of unique paths is 2.
Code (Java):
public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid == null || obstacleGrid.length == 0) {
            return 0;
        }
         
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
         
        if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) {
            return 0;
        }
         
        int[] dp = new int[n];
        dp[0] = 1;
         
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[j] = 0;
                } else if (j > 0) {
                    dp[j] = dp[j] + dp[j - 1];
                }
            }
        }
        return dp[n - 1];
    }
}


II. Sequence DP

  • f[i] stands for first i characters, numbers, etc..
  • f[i] = f[j], j <= i
  • Initial state: f[0]
  • Final state: f[n-1]
1. Climb chairs
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Code (Java):
public class Solution {
    public int climbStairs(int n) {
        if (n <= 1) {
            return 1;
        }
        
        int[] dp = new int[n];
        
        // Initialization
        dp[0] = 1;
        dp[1] = 2;
        
        for (int i = 2; i < n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        
        return dp[n-1];
    }
}

2. Jump Game
Given an array of non-negative integers, 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.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.
public class Solution {
    public boolean canJump(int[] A) {
        if (A == null || A.length == 0) {
            return true;
        }
        
        if (A[0] == 0 && A.length > 1) {
            return false;
        }
        
        boolean[] dp = new boolean[A.length];
        dp[0] = true;
        
        for (int i = 1; i < A.length; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] == true && j + A[j] >= i) {
                    dp[i] = true;
                    break;
                }
            }
        }
        
        return dp[A.length - 1];
        
    }
}

3. Jump Game II:
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
For example:
Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)
Code (Java):
public class Solution {
    public int jump(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }
        
        if (A[0] == 0 && A.length > 1) {
            return Integer.MAX_VALUE;
        }
        
        int[] dp = new int[A.length];
        
        // Initialization
        for (int i = 1; i < A.length; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        
        for (int i = 1; i < A.length; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] != Integer.MAX_VALUE && A[j] + j >= i) {
                    dp[i] = dp[j] + 1;
                    break;
                }
            }
        }
        
        return dp[A.length - 1];
    }
}


3. Longest Increasing Subsequence (LIS)
For [4, 2, 4, 5, 3, 7], the LIS is [4, 4, 5, 7], return 4

This is a sequence DP problem, so we define 

  • dp[N], whereas dp[i] denotes the length of the LIS including the array element arr[i]. 
  • Initial state: dp[i] = 1
  • Transit function: for each j, where 0 <= j < i, if (A[i] >= A[j]), dp[i] = Math.max(dp[i], dp[j] + 1);
  • Final state: result = 1, Math.max(result, dp[i]);
Code (Java):
public class Solution {
    /**
     * @param nums: The integer array
     * @return: The length of LIS (longest increasing subsequence)
     */
    public int longestIncreasingSubsequence(int[] nums) {
        // write your code here
        
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int[] dp = new int[nums.length];
        
        // Initialization
        for (int i = 0; i < nums.length; i++) {
            dp[i] = 1;
        }
        
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] <= nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        
        int result = 1;
        for (int i = 0; i < nums.length; i++) {
            result = Math.max(result, dp[i]);
        }
        
        return result;
    }
}
A wrong Solution:
Here is a wrong solution using the greedy idea. The basic idea is to use two loops, the outer loop i, starts from 0, and the inner loop starts from i + 1. For each inner loop, we scan through the array and compare the current value with the last one. The code is as follow:
Code (Java):
public class Solution {
    /**
     * @param nums: The integer array
     * @return: The length of LIS (longest increasing subsequence)
     */
    public int longestIncreasingSubsequence(int[] nums) {
        // write your code here
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        if (nums.length == 1) {
            return 1;
        }
        
        int maxLen = 1;
        for (int i = 0; i < nums.length; i++) {
            int prev = nums[i];
            int len = 1;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] >= prev) {
                    len++;
                    prev = nums[j];
                }
            }
            maxLen = Math.max(maxLen, len);
        }
        
        return maxLen;
    }
}
The code cannot pass the test case :
[10,1,11,2,12,3,11]
where the correct result is 4 (1, 2, 3, 11), but the solution above will generate 3, (1, 11, 12). That is because when j is at 11, it will ignore 2 and generate the incorrect results.


III. Two Sequence DP -- Usually given two strings
  • f[i][j] means the first i characters in the first sequence matches the the first j characters in the second sequence
  • Transit function: f[i][j] = figure out the relationship of i th character in sequence one and j th character in sequence two
  • Initial state: f[i][0], and f[0][i]
  • Final state: f[s1.length()][s2.length()]
1. Longest Common Subsequence (LCS)
Given two strings, find the longest comment subsequence (LCS).
Your code should return the length of LCS.
Example
For "ABCD" and "EDCA", the LCS is "A" (or D or C), return 1
For "ABCD" and "EACB", the LCS is "AC", return 2
Code (Java):
public class Solution {
    /**
     * @param A, B: Two strings.
     * @return: The length of longest common subsequence of A and B.
     */
    public int longestCommonSubsequence(String A, String B) {
        // write your code here
        if (A == null || B == null || A.length() == 0 || B.length() == 0) {
            return 0;
        }
        
        int m = A.length();
        int n = B.length();
        
        int[][] dp = new int[m + 1][n + 1];
        
        // initialization
        // not needed, as all are zero
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
               if (A.charAt(i - 1) == B.charAt(j - 1)) {
                   dp[i][j] = dp[i - 1][j - 1] + 1;
               } else {
                   dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
               }
            }
        }
        
        return dp[m][n];
    }
}


2. Edit Distance
Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character
Code (Java):
public class Solution {
    public int minDistance(String word1, String word2) {
        if (word1.length() == 0) {
            return word2.length();
        }
        
        if (word2.length() == 0) {
            return word1.length();
        }
        
        int m = word1.length();
        int n = word2.length();
        
        int[][] dp = new int[m + 1][n + 1];
        
        // initialization
        for (int i = 0; i <= n; i++) {
            dp[0][i] = i;
        }
        
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    int replace = dp[i - 1][j - 1] + 1;
                    int insert = dp[i][j - 1] + 1;
                    int delete = dp[i - 1][j] + 1;
                    
                    dp[i][j] = Math.min(replace, Math.min(insert, delete));
                }
            }
        }
        
        return dp[m][n];
    }
}

IV. Backpack
1. 0 / 1 back pack problem.
Given N non-negative integers and a target, Can we pick up any numbers from the N integers and its sum equals to the target. Return true of false
  • f[n + 1][Target]
  • f[i][S] Given First i numbers, can we pick up some numbers and their sums equal to S
  • Transit function: f[i][S] = f[i - 1][S- a[i]] (picked A[i])or f[i - 1][S] (not picked A[i])
  • Initial state: f[0][0] = true; f[0][1 ... SUM] = false;
  • Final state: f[n][target] .
Code (Java):
public class Solution {
    public boolean backpack(int[] A, int target) {
        if (A == null || A.length == 0 || target < 0) {
            return false;
        }
        
        boolean[][] dp = new boolean[A.length + 1][target + 1];
        dp[0][0] = true;
        
        for (int i = 1; i <= A.length; i++) {
            for (int j = 0; j <= target; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j - A[i - 1] >= 0) {
                    dp[i][j] = dp[i][j] || dp[i - 1][j - A[i - 1]];
                }
            }
        }
        return dp[A.length][target];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] A = new int[]{2,3,5,7};
        int target = 17;

        System.out.println(sol.backpack(A, target));
    
    }
} 

Note that target could equal to 0.

2. Lintcode: 0/1 Back pack II
13%
Accepted
Given n items with size A[i], an integer m denotes the size of a backpack. How full you can fill this backpack? 
Note
You can not divide any item into small pieces.
Example
If we have 4 items with size [2, 3, 5, 7], the backpack size is 11, we can select 2, 3 and 5, so that the max size we can fill this backpack is 10. If the backpack size is 12. we can select [2, 3, 7] so that we can fulfill the backpack.
You function should return the max size we can fill in the given backpack.
Understand the problem:
It is another 0/1 back pack problem. The crux of the problem is to pick up the item from the array of which the sum is cloest to the target value. 

So it is another DP problem, and we could define the DP functions.

  • dp[A.length() + 1][m + 1], where dp[i][j] means the sum that pick some from first i items of which the sum are cloest to j. 
  • Initial state: all 0s, so no need to initialize.
  • Transit function: dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - A[i]] + A[i]);
  • Final state: dp[A.length()][m].
Code (Java):
public class Solution {
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     */
    public int backPack(int m, ArrayList<integer> A) {
        // write your code here
        if (A == null || A.size() == 0 || m < 0) {
            return 0;
        }
        
        int[][] dp = new int[A.size() + 1][m + 1];
        
        
        // initialization
        // no needed since all 0s
        
        for (int i = 1; i <= A.size(); i++) {
            for (int j = 0; j <= m; j++) {
                int noPick = dp[i - 1][j];
                int pick = 0;
                
                if (j - A.get(i - 1) >= 0) {
                    pick = dp[i - 1][j - A.get(i - 1)] + A.get(i - 1);
                }
                
                dp[i][j] = Math.max(pick, noPick);
            }
        }
        
        return dp[A.size()][m];
    }
}

A 1D space DP solution:
Note that for back pack solution, the DP only relies on dp[i - 1], so we may reduce the space cost by using a 1D array. 

Code (Java):
public class Solution {
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     */
    public int backPack(int m, ArrayList&ltInteger&gt; A) {
        // write your code here
        if (A == null || A.size() == 0 || m < 0) {
            return 0;
        }
        
        //int[][] dp = new int[A.size() + 1][m + 1];
        int[] dp = new int[m + 1];
        
        // initialization
        // no needed since all 0s
        
        for (int i = 0; i < A.size(); i++) {
            //dp[0] = 0;
            for (int j = m; j >= 0; j--) {
                //int noPick = dp[i - 1][j];
                int noPick = dp[j];
                int pick = 0;
                
                if (j - A.get(i) >= 0) {
                    //pick = dp[i - 1][j - A.get(i - 1)] + A.get(i - 1);
                    pick = dp[j - A.get(i)] + A.get(i);
                }
                
                //dp[i][j] = Math.max(pick, noPick);
                dp[j] = Math.max(pick, noPick);
            }
        }
        
        return dp[m];
    }
}

Noted that the inner loop should start from the end in backward order. That is because we the result on dp[j] depends on dp[i - 1][j - A[i]]. So if we update the dp[j] from left to right, the previous results will be overwritten. 

3. A general 0/1 back pack problem:
http://www.geeksforgeeks.org/dynamic-programming-set-10-0-1-knapsack-problem/

Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. In other words, given two integer arrays val[0..n-1] and wt[0..n-1] which represent values and weights associated with n items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of val[] such that sum of the weights of this subset is smaller than or equal to W. 

Understand the problem:
The problem has two conditions to satisfy:
1. Pick up the some items from the array, such that 1. the sum of the value could reach the maximum, and 2. its weight should be less than the capacity W.

So we can solve the dp problem by defining the following:

  • dp[n + 1][W + 1], where dp[i][j] means from the first i items we choose some, and its weight sum is less than the j, as well as the value sum is maximal.
  • Initial state: 0.
  • Transit function: There should have two cases.
    • If wt[i] > j, we could not choose this item since it is over-weighted. In this case, dp[i][j] = dp[i - 1][j];
    • Else, dp[i][j] = Math.max(dp[i - 1][j] , dp[i - 1][j - wt[i]] + val[i]);
  • Final state: return dp[n][W]
Code (Java):
public class Solution {
    public int knapSack(int W, int[] val, int[] wt) {
        if (val == null || val.length == 0 || wt == null || wt.length == 0 || W <= 0) {
            return 0;
        }
        
        int[][] dp = new int[val.length + 1][W + 1];
        
        for (int i = 1; i <= val.length; i++) {
            for (int j = 0; j <= W; j++) {
                dp[i][j] = dp[i - 1][j]; // no pickup
                
                if (wt[i - 1] <= j) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - wt[i - 1]] + val[i - 1]);
                }
            }
        }
        
        return dp[val.length][W];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] val = new int[]{60, 100, 120};
        int[] wt = new int[]{10, 20, 30};
        int W = 50;

        System.out.println(sol.knapSack(W, val, wt));
    }
}

1D space Solution:
public class Solution {
    public int knapSack(int W, int[] val, int[] wt) {
        if (val == null || val.length == 0 || wt == null || wt.length == 0 || W <= 0) {
            return 0;
        }
        
        int[] dp = new int[W + 1];
        
        for (int i = 1; i <= val.length; i++) {
            for (int j = W; j >= 0; j--) {
                if (wt[i - 1] <= j) {
                    dp[j] = Math.max(dp[j], dp[j - wt[i - 1]] + val[i - 1]);
                }
            }
        }
        
        return dp[W];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] val = new int[]{60, 100, 120};
        int[] wt = new int[]{10, 20, 30};
        int W = 50;

        System.out.println(sol.knapSack(W, val, wt));
    }
}


4. A multiple DP problem -- Each item can be picked up by k times.
In this question, each element could be selected at most n[i] times. Find the maximum value with the sum of the weight less or equal to W. 

Again, the definition of the DP matrix is the same as above, ie,
dp[n + 1][W + 1], whereas dp[i][j] means picking the first i items with the sum of the weight less or equal to j, dp[i][j] is the maximum sum of the value. 

The transit function could be as follows:
dp[i][j] = Math.max(dp[i - 1][j - k * wt[i]] + k * val[i]), where as 0<= k <= n[i]

Code (Java):
public class Solution {
    public int knapSack(int W, int[] val, int[] wt, int[] n) {
        if (val == null || val.length == 0 || 
            wt == null || wt.length == 0 || 
            n == null || n.length == 0 || W <= 0) {
            
            return 0;
        }
        
        int[][] dp = new int[val.length + 1][W + 1];
        
        for (int i = 1; i <= val.length; i++) {
            for (int j = 0; j <= W; j++) {
                for (int k = 0; k <= n[i - 1]; k++) {
                    if (k * wt[i - 1] <= j) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * wt[i - 1]] + k * val[i - 1]);
                    }
                }
            }
        }
        
        return dp[val.length][W];       
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] val = new int[]{60, 100, 120};
        int[] wt = new int[]{10, 20, 30};
        int[] n = new int[]{100,100,100,100};
        int W = 50;

        System.out.println(sol.knapSack(W, val, wt, n));
    }
}

5. A multiple back pack problem -- each item can be picked up by unlimited number of times
In this case, we only need to change little of the code above. We change the inner most loop from k <= n[i - 1] to k * wt[i - 1] <= j.

Code (Java):


public class Solution {
    public int knapSack(int W, int[] val, int[] wt) {
        if (val == null || val.length == 0 || 
            wt == null || wt.length == 0 || 
            W <= 0) {
            
            return 0;
        }
        
        int[][] dp = new int[val.length + 1][W + 1];
        
        for (int i = 1; i <= val.length; i++) {
            for (int j = 0; j <= W; j++) {
                for (int k = 0; k * wt[i - 1] <= j; k++) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * wt[i - 1]] + k * val[i - 1]);
                }
            }
        }
        
        return dp[val.length][W];       
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] val = new int[]{60, 100, 120};
        int[] wt = new int[]{10, 20, 30};
        int[] n = new int[]{100,100,100,100};
        int W = 50;

        System.out.println(sol.knapSack(W, val, wt));
    }
}


Other back pack DP problems:
1. k sum
http://buttercola.blogspot.com/2014/11/lintcode-k-sum.html
http://www.lintcode.com/en/problem/k-sum/#

Given n distinct positive integers, integer k (k <= n) and a number target.
Find k numbers where sum is target. Calculate how many solutions there are?
Example
Given [1,2,3,4], k=2, target=5. There are 2 solutions:
[1,4] and [2,3], return 2.

Understand the problem:
It is another back pack problem, choosing k items out of n items, where its sum equals to k. 
So we could still use back pack DP solution.

Solution:
Idea: Using back pack dp

  • Definition:    dp[n + 1][k + 1][target + 1], where dp[i][j][m] means choosing j elements out of the first i elements, and its sum equals to m
  • Initial state:  dp[0][0][0] = 1, dp[i][0][0] = 1, 1 <= i <= n
  • Transit function:  
    • dp[i][j][m] = dp[i - 1][j][m]   // no choose item i
    • if (A[i - 1] <= m) dp[i][j][m] += dp[i - 1][j - 1][m - A[i - 1]]  // choose item i
  • Final state:  dp[n][k][target];
Code (Java):
public class Solution {
    /**
     * @param A: an integer array.
     * @param k: a positive integer (k <= length(A))
     * @param target: a integer
     * @return an integer
     */
    public int solutionKSum(int A[],int k,int target) {
        // write your code here
        if ((A == null || A.length == 0) && k == 0 && target == 0) {
            return 1;
        }
        
        if (A == null || A.length == 0 || k <= 0 || target <= 0 || k > A.length) {
            return 0;
        }
        
        int[][][] dp = new int[A.length + 1][k + 1][target + 1];
        dp[0][0][0] = 1;
        for (int i = 1; i <= A.length; i++) {
            dp[i][0][0] = 1;
        }
        
        for (int i = 1; i <= A.length; i++) {
            for (int j = 1; j <= k; j++) {
                for (int m = 1; m <= target; m++) {
                    dp[i][j][m] = dp[i - 1][j][m]; // no choose item i
                    
                    if (A[i - 1] <= m) {
                        dp[i][j][m] += dp[i - 1][j - 1][m - A[i - 1]]; // chose item i
                    }
                }
            }
        }
        return dp[A.length][k][target];
    }
}






1 comment:

  1. 4 line 16:
    [j - k * wt[i - 1]] + k * val[i - 1]

    ReplyDelete