Dynamic Programming

归纳总结

1. 优化问题，通常都会让你找最小，最大，最少，最多。。。

2. 可以拆分成小问题，小问题 => 大问题。即，当前的运算只基于前面的结果，而和之后的结果没有关系。

3. 某些时候，可以以要求解的参数为index，如要求解最小步数，那么可以以步数为index

   e.g.1 Minimum Number of Refueling Stops

4. 通常情况下，对于每一个点，有“选择“和“不选择“两种状态，相当于两条不同的合流，取哪一条，怎么取，要看题意。

   e.g.1 House Robber

   e.g.2 House Robber II

   e.g.3 House Robber III

   e.g.4 Minimum Swaps to make sequences increasing

5. Substring Search

   e.g.1 Edit Distance

   e.g.2 Maximum Length of Repeated Subarray

   e.g.3 Valid Palindrome

经典题目

55 Jump Game 45 Jump Game II

55 Jump Game

// Keep a variable to record the maximum index we can jump to so far.

public boolean canJump(int[] nums) {
    if (nums == null || nums.length == 0) return true;
    int max = nums[0];
    for (int i = 1; i < nums.length; i++) {
        if (i > max) {
            return false;
        }
        max = Math.max(max, i + nums[i]);
    }
    return true;
}

45 Jump Game II

276 Paint Fence

class Solution {
    public int numWays(int n, int k) {
        if (k == 0 || n == 0) return 0;
        if (n == 1) return k;
        
        int same = k;
        int notSame = k * (k - 1);
        
        for (int i = 3; i <= n; i++) {
            int tmp = same;
            same = notSame;
            notSame = (k - 1) * (tmp + notSame);
        }
        
        return same + notSame;
    }
}

72 Edit Distance

/*
    a = "pale"
    b = "ple"

        0('')    1('p')    2('l')    3('e')
0('')    0         1        2         3
1('p')   1         0        1         2
2('a')   2         1        1         2
3('l')   3         2        1         2
4('e')   4         3        2         1

dp[i][j] : min edit distance between a[0, i] and b[0, j]
dp[i][j] = dp[i - 1][j - 1],         a[i] == b[j]
     1. remove a[i]:  dp[i - 1][j] + 1 
     2. insert b[j] to a[i]:  dp[i][j - 1] + 1     a[i] != b[j]
     3. replace: dp[i - 1][j - 1] + 1
*/

public int minDistance(String word1, String word2) {
    int n = word1.length();
    int m = word2.length();
    int[][] rs = new int[n + 1][m + 1];
    for (int i = 1; i <= n; i++) {
        rs[i][0] = i;
    }
    for (int j = 1; j <= m; j++) {
        rs[0][j] = j;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            rs[i][j] = Integer.MAX_VALUE; 
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                rs[i][j] = rs[i - 1][j - 1];
            } else {
                rs[i][j] = Math.min(rs[i - 1][j] + 1, rs[i][j]);
                rs[i][j] = Math.min(rs[i][j - 1] + 1, rs[i][j]);
                rs[i][j] = Math.min(rs[i - 1][j - 1] + 1, rs[i][j]);
            }
        }
    }
    return rs[n][m];
}

91 Decode Ways

// Method 2: DP. One Pass.
// LeetCode Runtime: 1ms. Extremely fast.
public int numDecodings(String s) {
	// dp[i] : number of ways to decode s[i, n - 1]
	// dp[i] = {dp[i + 1]} + {dp[i + 2]};
    int[] dp = new int[s.length() + 1];
    dp[s.length()] = 1;
    
    for (int i = s.length() - 1; i >= 0; i--) {
		// Condition 1: choose only one char
        char next = s.charAt(i);
        if (next != '0') {
            dp[i] += dp[i + 1];
        }
			
		// Condition 2: choose two chars
        if (i + 1 < s.length()) {
            char nextNext = s.charAt(i + 1);
            int num = (next - '0') * 10 + (nextNext - '0');
            if (num >= 10 && num <= 26) {
                dp[i] += dp[i + 2];
            }
        }
    }
    return dp[0];
}

152 Maximum Product Subarray

这道题跟 maximum subarray sum 的区别在于，乘法可以负负得正，也就是说当前最小的值也有可能变成最大的值。所以我们需要同时记录当前最大和最小的数。

这里的当前，means ending here (including the current element)

Space O(n)

public int maxProduct(int[] nums) {
    int[] l = new int[nums.length];
    int[] s = new int[nums.length];
    l[0] = nums[0];
    s[0] = nums[0];
    int max = nums[0];
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] > 0) {
            l[i] = Math.max(nums[i], nums[i] * l[i - 1]);
            s[i] = Math.min(nums[i], nums[i] * s[i - 1]);
        } else if (nums[i] < 0) {
            l[i] = Math.max(nums[i], nums[i] * s[i - 1]);
            s[i] = Math.min(nums[i], nums[i] * l[i - 1]);
        }
        max = Math.max(max, l[i]);
    }
    return max;
}

Constant Space

174 Dungeon Game

dp[i][j]: the minimum of health needed at the current cell to reach the bottom-right cell.

public int calculateMinimumHP(int[][] dungeon) {
    int n = dungeon.length;
    int m = dungeon[0].length;
    int[][] dp = new int[n][m];
    for (int i = n - 1; i >= 0; i--) {
        for (int j = m - 1; j >= 0; j--) {
            int min = Integer.MAX_VALUE;
            if (j + 1 < m) {
                min = Math.min(min, dp[i][j + 1]);
            }
            if (i + 1 < n) {
                min = Math.min(min, dp[i + 1][j]);
            }
            if (min == Integer.MAX_VALUE) {
                min = 1;
            }
            // This means we need to offer more energy to the knight to make it possible moving to the next cell.
            if (min - dungeon[i][j] > 0) {
                dp[i][j] = min - dungeon[i][j];
            } 
            // We have enough energy to reach the bottom-right cell, so we just need to make sure the knight is alive.
            else {
                dp[i][j] = 1;
            }
        }
    }
    return dp[0][0];
}

300 Longest Increasing Subsequence 873 Length of Longest Fibonacci Subsequence

300 Normal DP

# Time: O(n^2)
# Space: O(n)
def lengthOfLIS(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    # dp[i] represents the longest length of increasing sequence ending at index i (included)
    if nums is None or len(nums) == 0:
        return 0
    dp = []
    dp.append(1)
    ans = 1
    for i in range(1, len(nums)):
        val = 1
        for j in range(0, i):
            if nums[i] > nums[j]:
                val = max(val, dp[j] + 1)
        dp.append(val)
        ans = max(ans, val)
    return ans

300 DP & Binary Search

873 DP

718 Maximum Length of Repeated Subarray

public int findLength(int[] A, int[] B) {
    int[][] dp = new int[A.length][B.length];
    int max = 0;
    for (int i = 0; i < A.length; i++) {
        for (int j = 0; j < B.length; j++) {
            if (A[i] == B[j]) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
            }
            max = Math.max(max, dp[i][j]);
        }
    }
    return max;
}

871 Minimum Number of Refueling Stops

我们以步数为index，构建dp array。dp[i] 代表停 i 次可以走的最远距离。 那么，每次到一个新的站点时，有停或不停两种选择，当然前提是要能到达这个站点。 所以，dp[j + 1] = max(dp[j + 1], dp[j] + stations[i][1]), if dp[j] >= stations[i][0]

DP Sol

public int minRefuelStops(int target, int startFuel, int[][] stations) {
    long[] dp = new long[stations.length + 1];
    dp[0] = startFuel;
    for (int i = 0; i < stations.length && target > stations[i][0]; i++) {
        for (int j = i; j >= 0; j--) {
            if (dp[j] >= stations[i][0]) {
                dp[j + 1] = Math.max(dp[j + 1], dp[j] + stations[i][1]);
            }                   
        }
    }
    for (int i = 0; i <= stations.length; i++) {
        if (dp[i] >= target) return i;
    }
    return -1;
}

PriorityQueue Sol

680 Valid Palindrome II Variant: Given a string and a num k of how many chars you can delete, return true if you can make the string palindrome

516 Longest Palindromic Subsequence

680 Sol

public boolean validPalindrome(String s) {
    if (s == null || s.length() == 0) return true;
    int left = 0, right = s.length() - 1;
    int count = 0;
    
    while(left < right) {
        if (s.charAt(left) != s.charAt(right)) {
            if (count == 0) {
                return isPalindrome(left + 1, right, s) || isPalindrome(left, right - 1, s);
            } else {
                return false;
            }
        }
        left++;
        right--;
    }
    return true;
}

private boolean isPalindrome(int l, int r, String s) {
    while (l < r) {
        if (s.charAt(l) != s.charAt(r)) return false;
        l++;
        r--;
    }
    return true;
}

Varient

516 Sol

801. Minimum Swaps To Make Sequences Increasing

public int minSwap(int[] A, int[] B) {
    // swap : minimum number of swaps to make A[0, i - 1] increasing, and A[i - 1] is swapped if necessary
    // unswap: minimum number of swaps to make A[0, i - 1] increasing, and A[i - 1] is unswapped if necessary
    int swap = 1, unswap = 0;
    for (int i = 1; i < A.length; i++) {
        int newSwap = A.length, newUnswap = A.length;
        // Condition 1:
        // Both of A[i - 1] and A[i] need to be swapped or unswapped
        if (A[i - 1] < A[i] && B[i - 1] < B[i]) {
            // Both unswap
            newUnswap = Math.min(newUnswap, unswap);
            // Both swap
            newSwap = Math.min(newSwap, swap + 1);
        }
        
        // Condition 2:
        // One of A[i - 1] and A[i] need to be swapped or unswapped
        if (A[i - 1] < B[i] && B[i - 1] < A[i]) {
            // Swap A[i - 1]
            newUnswap = Math.min(newUnswap, swap);
            // Swap A[i]
            newSwap = Math.min(newSwap, unswap + 1);
        }
        
        // Update swap and unswap
        swap = newSwap;
        unswap = newUnswap;
    }
    return Math.min(swap, unswap);
}