Leetcode Dymanic Programming Problems Summary 动态规划总结

What is dynamic programming (DP) ?

 

1.      Has optimal substructure: can be broken into subproblems and find solutions to subproblems
2.      Subproblems are used multiple times : use memorization to compute only once and save time.
3.      Subproblem solutions will not change

 

Top down:DFS + memorization

Bottom up: DP

Steps to Solve DP

 

1. Definition of State Function
2. Induction Rule
3. Base Case
4. Result

 

Fibinnaci Sequence application:  LC. 70 Climb Stairs https://leetcode.com/problems/climbing-stairs/description/

dp[1] = 1;

    dp[2] = 2;

    for (int i = 3; i <= n; i++) {

        dp[i] = dp[i – 1] + dp[i – 2];

    }

    return dp[n];

2D array path series

Unique path:

for (int i = 0; i < m; i++) {

        for (int j = 0; j < n; j++) {

            if (i == 0 || j == 0) {

               dp[i][j] = 1;

                   continue;

            }

               dp[i][j] = dp[i – 1][j] + dp[i][j – 1];

        }

    }

    return dp[m – 1][n – 1];

Follow up? With obstacles?

unique path 2

if (obstacleGrid[i][j] == 1) {

                   dp[i][j] = 0;

 

Minimum Path Sum

 

sum[i][j] = Math.min(sum[i – 1][j], sum[i][j – 1]) + grid[i][j];

 

Dungeon Game  (Hard)

 

for (int i = m – 1; i >= 0; i–) {

           for (int j = n – 1; j >= 0; j–) {

               if (i == m – 1 && j == n – 1) {

                   dp[i][j] = Math.max(1, 1 – dungeon[i][j]);

               } else if (i == m – 1) {

                   dp[i][j] = Math.max(1, dp[i][j + 1] – dungeon[i][j]);

               } else if (j == n – 1) {

                   dp[i][j] = Math.max(1, dp[i + 1][j] – dungeon[i][j]);

               } else {

                   dp[i][j] = Math.max(1, Math.min(dp[i + 1][j], dp[i][j + 1]) – dungeon[i][j]);

               }

           }

       }

 

House Robber

for (int i = 2; i < nums.length; i++) {

           dp[i] = Math.max(dp[i – 1], dp[i – 2] + nums[i]);

       }

       return dp[nums.length – 1];

 

House Robber II

return Math.max(helper(nums, 1, nums.length – 1), helper(nums, 2, nums.length – 2) + nums[0]);

Paint House

for(int i=1; i<costs.length; i++){

       costs[i][0] += Math.min(costs[i-1][1],costs[i-1][2]);

       costs[i][1] += Math.min(costs[i-1][0],costs[i-1][2]);

       costs[i][2] += Math.min(costs[i-1][1],costs[i-1][0]);

   }

 

Paint House II  k colors?

int prevMin = 0;

       int prevSecond = 0;

       int prevIndex = 0;

       for (int i = 0; i < costs.length; i++) {

           int curMin = Integer.MAX_VALUE;

           int secondMin = Integer.MAX_VALUE;

           int curIndex = -1;

           for (int j = 0; j < costs[0].length; j++) {

               costs[i][j] = costs[i][j] + (j == prevIndex ? prevSecond : prevMin);

               if (costs[i][j] <= curMin) {

                   secondMin = curMin;

                   curMin = costs[i][j];

                   curIndex = j;

               } else if (costs[i][j] <= secondMin) {

                   secondMin = costs[i][j];

               }

           }

           prevMin = curMin;

           prevSecond = secondMin;

           prevIndex = curIndex;

       }

 

Paint Fence

int[] same = new int[n];

       int[] diff = new int[n];

       same[0] = same[1] = k;

       diff[0] = k;

       diff[1] = k * (k – 1);

       for (int i = 2; i < n; i++) {

           same[i] = diff[i – 1];

           diff[i] = (same[i – 1] + diff[i – 1]) * (k – 1);

       }

       return same[n – 1] + diff[n – 1];

 

Maximum Product Subarray

for (int i = 1; i < nums.length; i++) {

           max[i] = Math.max(Math.max(max[i – 1] * nums[i], min[i – 1] * nums[i]), nums[i]);

           min[i] = Math.min(Math.min(max[i – 1] * nums[i], min[i – 1] * nums[i]), nums[i]);

           res = Math.max(res, max[i]);

       }

 

Maximum Subarray

int max= Integer.MIN_VALUE;

       int sum = 0;

       for (int i = 0; i < nums.length; i++) {

           sum += nums[i];

           sum = Math.max(sum, nums[i]);

           max = Math.max(sum, max);

       }

       return max;

 

Arithmetic Slices

int cur = 0;

       int sum = 0;

       for (int i = 2; i < A.length; i++) {

           if (A[i] – A[i – 1] == A[i – 1] – A[i – 2]) {

               cur += 1;

               sum += cur;

           } else {

               cur = 0;

           }

       }

       return sum;

 

Continuous Subarray Sum

Map<Integer, Integer> map = new HashMap<>();

       map.put(0, -1);

       int sum = 0;

       for (int i = 0; i < nums.length; i++) {

           sum += nums[i];

           if (k != 0) {

               sum = sum % k;

           }

           if (map.containsKey(sum)) {

               if (i – map.get(sum) > 1) {

                   return true;

               }

           } else {

               map.put(sum, i);

           }

               

       }

 

Longest Palindromic Subsequence

for (int i = length – 1; i >= 0; i–) {

           dp[i][i] = 1;

           for (int j = i + 1; j < length; j++) {

               if (s.charAt(i) == s.charAt(j)) {

                   dp[i][j] = dp[i + 1][j – 1] + 2;

               } else {

                   dp[i][j] = Math.max(dp[i + 1][j], dp[i][j – 1]);

               }

           }

       }

       return dp[0][length – 1];

 

Longest Palindromic Substring

for (int i = n – 1; i >= 0; i–) {

           for (int j = i; j < n; j++) {

               if (s.charAt(i) == s.charAt(j) && (j – i < 3 || dp[i + 1][j – 1])) {

                   dp[i][j] = true;

               }

               if (dp[i][j] && (res == null || j – i + 1 > res.length())) {

                    res = s.substring(i, j + 1);

               }

           }

       }

 

Word Break   dp[0] = true;        for (int i = 1; i <= s.length(); i++) {            for (int j = 0; j <= i – 1; j++) {                if (dp[j] && set.contains(s.substring(j, i))) {                    dp[i] = true;                    continue;                }            }        }        return dp[s.length()];

Word Break II   

for (int i = 1; i <= s.length(); i++) {

           LinkedList<String> list = new LinkedList<>();

           for (int j = 0; j < i; j++) {

               if (dp[j].size() > 0 && wordDict.contains(s.substring(j, i))) {

                   for (String l : dp[j]) {

                       list.add(l + (l.equals(“”) ? “” : ” “) + s.substring(j, i));

                   }

               }

           }

           dp[i] = list;

       }

       return dp[s.length()];

 

Distinct Subsequences

for (int i = 1; i <= s.length(); i++) {

           for (int j = 1; j <= t.length(); j++) {

               dp[i][j] = dp[i – 1][j] + (s.charAt(i – 1) == t.charAt(j – 1) ? dp[i – 1][j – 1] : 0);

           }

       }

       return dp[s.length()][t.length()];

 

Longest Increasing Subsequence

int[] dp = new int[nums.length];

       dp[0] = 1;

       int maxans = 1;

       for (int i = 1; i < dp.length; i++) {

           int maxval = 0;

           for (int j = 0; j < i; j++) {

               if (nums[i] > nums[j]) {

                   maxval = Math.max(maxval, dp[j]);

               }

           }

           dp[i] = maxval + 1;

           maxans = Math.max(maxans, dp[i]);

       }

       return maxans;

 

Coin Change

for (int i = 1; i <= amount; i++) {

           dp[i] = Integer.MAX_VALUE;

           for (int j = 0; j < n; j++) {

               if (i – coins[j] >= 0 && dp[i – coins[j]] != Integer.MAX_VALUE) {

                   dp[i] = Math.min(dp[i], dp[i – coins[j]] + 1);

               }

           }

       }

       return dp[amount] == Integer.MAX_VALUE? -1 : dp[amount];

 

Coin Change 2    

dp[0][0] = 1;

       for(int i = 1; i <= coins.length; i++) {

           dp[i][0] = 1;

           for (int j = 1; j <= amount; j++) {

               dp[i][j] = dp[i – 1][j] + (j >= coins[i – 1] ? dp[i][j – coins[i – 1]] : 0);

           }

       }

       return dp[coins.length][amount];

 

Partition Equal Subset Sum    

for (int i = 1; i < n+1; i++) {

           dp[i][0] = true;

       }

       for (int j = 1; j < sum+1; j++) {

           dp[0][j] = false;

       }

 

       for (int i = 1; i < n+1; i++) {

           for (int j = 1; j < sum+1; j++) {

               dp[i][j] = dp[i-1][j];

               if (j >= nums[i-1]) {

                   dp[i][j] = (dp[i][j] || dp[i-1][j-nums[i-1]]);

               }

           }

       }

 

       return dp[n][sum];

 

Best Time to Buy and Sell Stock    

int min = Integer.MAX_VALUE;
       int max = 0;
       for (int i = 0; i < prices.length; i++) {
           min = Math.min(prices[i], min);
           max = Math.max(prices[i] – min, max);
       }
       return max;

Best Time to Buy and Sell Stock II

int max = 0;

       for (int i = 1; i < prices.length; i++) {

           if (prices[i] >= prices[i – 1]) {

               max += prices[i] – prices[i – 1];

           }

       }

       return max;

 

Best Time to Buy and Sell Stock III  

int buy1 = Integer.MAX_VALUE;

       int sell1 = 0;

       int buy2 = Integer.MAX_VALUE;

       int sell2 = 0;

       for (int i = 0; i < prices.length; i++) {

           buy1 = Math.min(buy1, prices[i]);

           sell1 = Math.max(sell1, prices[i] – buy1);

           buy2 = Math.min(buy2, prices[i] – sell1);

           sell2 = Math.max(sell2, prices[i] – buy2);

       }

       return sell2;

 

Decode Ways

for (int i = 2; i <= s.length(); i++) {

           int first = Integer.valueOf(s.substring(i – 1, i));

           int second = Integer.valueOf(s.substring(i – 2, i));

           if (first >= 1 && first <= 9) {

               dp[i] += dp[i – 1];

           }

           if (second <= 26 && second >= 10) {

               dp[i] += dp[i – 2];

           }

       }

       return dp[s.length()];

 

Decode Ways II

 

Wildcard Matching    for (int i = 1; i <= m; i++) {            for (int j = 1; j <= n; j++) {                if (pc[j – 1] == ‘?’ || pc[j – 1] == sc[i – 1]) {                    dp[i][j] = dp[i – 1][j – 1];                } else if (pc[j – 1] == ‘*’) {                    dp[i][j] = dp[i][j – 1] || dp[i – 1][j];                }            }        }        return dp[m][n];

 

Regular Expression Matching

       int m = p.length();

       int n = s.length();

       boolean[][] dp = new boolean[m+1][n+1];

       dp[0][0] = true;

       for (int i = 1; i <= m; i++){

           if (p.charAt(i-1) == ‘*’){

               dp[i][0] = dp[i-1][0] || dp[i-2][0];

           }

       }

       for (int i = 1; i <= m; i++){

           for (int j = 1; j <= n; j++){

               if (p.charAt(i-1) == s.charAt(j-1) || p.charAt(i-1) == ‘.’){

                   dp[i][j] = dp[i-1][j-1];

               }else if (p.charAt(i-1) == ‘*’){

                   if (i > 1 && p.charAt(i-2) != s.charAt(j-1) && p.charAt(i-2) != ‘.’){

                       dp[i][j] = dp[i-2][j];

                   }else if (i > 1 && (p.charAt(i-2) == s.charAt(j-1) || p.charAt(i-2) == ‘.’)){

                       dp[i][j] = dp[i-2][j] || dp[i-2][j-1] || dp[i][j-1];

                   }else{

                       dp[i][j] = false;

                   }

               }

           }

       }

       return dp[m][n];