Dynamic Programming
归纳总结
优化问题，通常都会让你找最小，最大，最少，最多。。。
可以拆分成小问题，小问题 => 大问题。即，当前的运算只基于前面的结果，而和之后的结果没有关系。
某些时候，可以以要求解的参数为index，如要求解最小步数，那么可以以步数为index
通常情况下，对于每一个点，有“选择“和“不选择“两种状态，相当于两条不同的合流，取哪一条，怎么取，要看题意。
e.g.1 House Robber
e.g.2 House Robber II
e.g.3 House Robber III
经典题目
// 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;
}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;
}
}/*
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];
}// 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];
}这道题跟 maximum subarray sum 的区别在于，乘法可以负负得正，也就是说当前最小的值也有可能变成最大的值。所以我们需要同时记录当前最大和最小的数。
这里的当前，means ending here (including the current element)
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;
}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
# 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 ans718 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]
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;
}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
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;
}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);
}Last updated