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

/*
    Similar to Jump Game, we keep a variable to record the maximum index 
    we can jump to so far. In order to obtain that number, 
    we should calculate the one step distance every time we reach a new index. 
    Then, when we reach the current maximum index, 
    we should increase the number of steps by 1 and 
    update our current maximum index to the current maximum one step distance.
*/
public int jump(int[] nums) {
    final int INVALID = 0;
    if (nums == null || nums.length <= 1) return INVALID;
    int steps = 0, curFarest = 0, curEnd = 0;
    for (int i = 0; i < nums.length - 1; i++) {
        if (i > curFarest) {
            break;
        }
        curEnd = Math.max(curEnd, i + nums[i]);
        if (i == curFarest) {
            steps += 1;
            curFarest = curEnd;
        }
    }
    return curFarest >= nums.length - 1 ? steps : INVALID;
}

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

// Optimize Space
public int maxProduct(int[] nums) {
    int max = nums[0];
    int min = nums[0];
    int res = nums[0];
    for (int i = 1; i < nums.length; i++) {
        int temp = max;
        max = Math.max(nums[i], Math.max(temp * nums[i], min * nums[i]));
        min = Math.min(nums[i], Math.min(temp * nums[i], min * nums[i]));
        res = Math.max(res, max);
    }
    return res;
}

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

def lengthOfLIS(self, nums):
    # dp[i] represents the smallest ending value of all the ascending sequences with length i  
    if nums is None or len(nums) == 0:
        return 0

    dp = []

    # Initialization
    # We have an ascending sequence of length 1, ending value as nums[0]
    dp.append(0)
    dp.append(nums[0])

    for i in range(1, len(nums)):
        num = nums[i]
        index = self.helper(dp, num)

        if index + 1 == len(dp):
            dp.append(num)
        else:
            dp[index + 1] = num

    return len(dp) - 1

# find the largest smaller number than num in dp and return the index
def helper(self, dp, num):
    left = 1
    right = len(dp) - 1
    while left <= right:
        mid = left + (right - left) / 2
        if dp[mid] >= num:
            right = mid - 1
        else:
            left = mid + 1
    return right

873 DP

// HashMap([i, j]) : longest length ending with [i, j]
// HashMap([j, k]) = max(HashMap([i, j])) + 1, if A[i] + A[j] = A[k]

class Solution {
    public int lenLongestFibSubseq(int[] A) {
        Map<Integer, Integer> index = new HashMap<>();
        for (int i = 0; i < A.length; i++) index.put(A[i], i);
        Map<Integer, Integer> longest = new HashMap<>();
        int max = 0;
        for (int k = 2; k < A.length; k++) {
            for (int j = k - 1; j >= 1; j--) {
                int i = index.getOrDefault(A[k] - A[j], -1);
                if (i >= 0 && j > i) {
                    // we have two pairs now: 
                    // [i, j] and [j, k]
                    // longest([j, k]) = longest([i, j]) + 1, if i + j == k
                    int length = longest.getOrDefault(i * A.length + j, 2) + 1;
                    longest.put(j * A.length + k, length);
                    max = Math.max(length, max);
                }
            }
        }
        return max;
    }
}

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

// The idea is try to check all the stops we can reach currently,
// and pick the one with most gas in it, increment the remaining gas,
// and increment the count. Keep doing this until we reach the target.

public int minRefuelStops(int target, int startFuel, int[][] stations) {
    PriorityQueue<Integer> pq = new PriorityQueue<>();
    int dist = startFuel;
    int stop = 0;
    int index = 0;
    while (true) {
        while (index < stations.length && dist >= stations[index][0]) {
            pq.add(-stations[index][1]);
            index++;
        }
        if (dist >= target) return stop;
        if (pq.isEmpty()) return -1;
        dist += -pq.poll();
        stop++;
    }
}

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

// DP

public boolean validPalindrome(String s, int k) {
    if (s == null || s.length() == 0) return true;
    int n = s.length();
    int[][] dp = new int[n][n];
    
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i + 1; j < n; j++) {
            if (s.charAt(i) == s.charAt(j)) {
                if (j == i + 1) {
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = dp[i + 1][j - 1];
                }
            } else {
                dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1;
            }
        }
    }
    return dp[0][s.length() - 1] <= k;
}

516 Sol

public int longestPalindromeSubseq(String s) {
    // dp[i][j]: longest palindrome within s[i, j]
    // dp[i][j] = dp[i + 1][j - 1], if i < a <= b < j && s[i] == s[j]
    //            max(dp[i + 1][j], dp[i][j - 1]), otherwise
    // base case: dp[i][i] = 1
    int n = s.length();
    int[][] dp = new int[n][n];
    for (int i = 0; i < n; i++) {
        dp[i][i] = 1;
    }
    for (int i = n - 2; i >= 0; i--) {
        for (int j = i + 1; j < n; j++) {
            if (s.charAt(i) == s.charAt(j)) {
                if (j == i + 1) {
                    dp[i][j] = 2;
                } else {
                    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][n - 1];
}

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);
}