動態(tài)規(guī)劃
[TOC]
單串問題
5.最長回文子串
-
解題要點：二維動態(tài)規(guī)劃，通過
dp[j + 1][i - 1]推導dp[j][i]public String longestPalindrome(String s) { if (s == null || s.length() == 0) { return ""; } String result = String.valueOf(s.charAt(0)); boolean[][] dp = new boolean[s.length()][s.length()]; for (int i = 0; i < s.length(); i++) { dp[i][i] = true; } for (int i = 1; i < s.length(); i++) { for (int j = i - 1; j >= 0; j--) { if ((dp[j + 1][i - 1] || i - j < 2) && s.charAt(j) == s.charAt(i)) { dp[j][i] = true; if (i - j + 1 > result.length()) { result = s.substring(j, i + 1); } } } } return result; }
300.最長遞增子序列
-
二維動態(tài)規(guī)劃經(jīng)典問題谷醉。dp[i] = max{dp[j], 0 <= j < i}
public int lengthOfLIS(int[] nums) { int[] dp = new int[nums.length]; Arrays.fill(dp, 1); int maxLen = dp[0]; for (int i = 1; i < nums.length; i++) { for (int j = 0; j < i; j++) { if (nums[i] > nums[j]) { dp[i] = Math.max(dp[i], dp[j] + 1); maxLen = Math.max(maxLen, dp[i]); } } } return maxLen; } -
上述解法通過構造不同含義的動態(tài)規(guī)劃方程并借助二分查找優(yōu)化時間復雜度為
O(nlogn)public int lengthOfLIS(int[] nums) { int[] dp = new int[nums.length]; //dp[i] 表示 i 個元素的子序列最后一個元素的最小值 int res = 0; for (int num: nums) { int l = 0, r = res; while (l < r) { int m = l + (r - l) / 2; if (dp[m] < num) { l = m + 1; } else { r = m; } } dp[l] = num; // dp[l] <= num <= dp[r] if (r == res) { // num > dp[r]屈糊，子序列遞增一個。 res++; } } return res; }
673. 最長遞增子序列的個數(shù)
-
求最長遞增子序列，同時計算每個長度遞增子序列的長度吮廉。
public int findNumberOfLIS(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int[] length = new int[nums.length]; int[] count = new int[nums.length]; length[0] = 1; count[0] = 1; for (int i = 1; i < nums.length; i++) { length[i] = 1; count[i] = 1; for (int j = i - 1; j >= 0; j--) { if (nums[i] > nums[j]) { if (length[i] < length[j] + 1) { // 以 num[i] 結尾的子序列長度有增長 length[i] = length[j] + 1; count[i] = count[j]; // 拼接 以 num[j] 結尾的最長子序列 } else if(length[i] == length[j] + 1) { count[i] += count[j]; // 新增 count[j] 個長度為 length[i] 的子序列 } } } } int maxLength = Arrays.stream(length).max().getAsInt(); int res = 0; for (int i = 0; i < nums.length; i++) { if (length[i] == maxLength) { res += count[i]; } } return res; }
354. 俄羅斯套娃信封問題
- 先排序移宅，然后在數(shù)組第二個維度上子最長遞增子序列問題鲫售。
public int maxEnvelopes(int[][] envelopes) {
Arrays.sort(envelopes, (a, b) -> {
if (a[0] == b[0]) {
return b[1] - a[1];
}
return a[0] - b[0];
});
int[] dp = new int[envelopes.length];
Arrays.fill(dp, 1);
int maxLen = dp[0];
for (int i = 1; i < envelopes.length; i++) {
for (int j = 0; j < i; j++) {
if (envelopes[i][1] > envelopes[j][1]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
maxLen = Math.max(maxLen, dp[i]);
}
}
}
return maxLen;
}
53. 最大子序和
-
dp[i] 表示以 num[i] 結尾的最大子數(shù)組和。
public int maxSubArray(int[] nums) { int[] dp = new int[nums.length]; dp[0] = nums[0]; int maxSum = dp[0]; for (int i = 1; i < nums.length; i++) { dp[i] = Math.max(dp[i - 1], 0) + nums[i]; maxSum = Math.max(maxSum, dp[i]); } return maxSum; }
152. 乘積最大子數(shù)組
-
與最大子序和類似径筏，乘法需要考慮正負號葛假，所以需要最大 dp 數(shù)組和最小 dp 數(shù)組。
public int maxProduct(int[] nums) { int[] minProduct = new int[nums.length]; int[] maxProduct = new int[nums.length]; minProduct[0] = nums[0]; maxProduct[0] = nums[0]; int maxRes = maxProduct[0]; for (int i = 1; i < nums.length; i++) { maxProduct[i] = Math.max(maxProduct[i - 1] * nums[i], Math.max(nums[i], minProduct[i - 1] * nums[i])); minProduct[i] = Math.min(minProduct[i - 1] * nums[i], Math.min(nums[i], maxProduct[i - 1] * nums[i])); maxRes = Math.max(maxRes, maxProduct[i]); } return maxRes; }
918. 環(huán)形子數(shù)組的最大和
-
分兩種情況：
- 不同時包含首尾元素滋恬，直接求最大子數(shù)組和
- 同時包含首尾元素聊训，求 num[1...length - 2] 最小子數(shù)組和，然后用整個數(shù)組和相減恢氯。
public int maxSubarraySumCircular(int[] A) { if (A.length < 2) { return A[0]; } int maxSum = A[0]; int curr = A[0]; int sum = A[0]; for (int i = 1; i < A.length; i++) { curr = Math.max(curr + A[i], A[i]); maxSum = Math.max(curr, maxSum); sum += A[i]; } int minSum = A[1]; curr = A[1]; for (int i = 2; i < A.length - 1; i++) { curr = Math.min(curr + A[i], A[i]); minSum = Math.min(minSum, curr); } return Math.max(sum - minSum, maxSum); }
面試題 17.24. 最大子矩陣
-
將第 i...j 行的矩陣的列方向和求出带斑，然后在這個列向和數(shù)組上求最大子數(shù)組和。
public int[] getMaxMatrix(int[][] matrix) { int[] result = new int[4]; int maxSum = matrix[0][0]; for (int i = 0; i < matrix.length; i++) { int[] sum = new int[matrix[i].length]; for (int j = i; j < matrix.length; j++) { int start = 0; int curr = 0; for (int k = 0; k < matrix[i].length; k++) { sum[k] += matrix[j][k]; curr += sum[k]; if (curr > maxSum) { result[0] = i; result[1] = start; result[2] = j; result[3] = k; maxSum = curr; } if (curr < 0) { start = k + 1; curr = 0; } } } } return result; }
363. 矩形區(qū)域不超過 K 的最大數(shù)值和
-
子矩陣求和勋拟，然后通過 TreeSet 保存 sum[0...i] 勋磕，找到 i，j 使得 sum[j] - sum[i] <= k敢靡。
public int maxSumSubmatrix(int[][] matrix, int k) { int ans = Integer.MIN_VALUE; for (int i = 0; i < matrix.length; i++) { int[] sum = new int[matrix[i].length]; for (int j = i; j < matrix.length; j++) { int curr = 0; TreeSet<Integer> sumSet = new TreeSet<>(); sumSet.add(0); for (int col = 0; col < matrix[i].length; col++) { sum[col] += matrix[j][col]; curr += sum[col]; Integer tmp = sumSet.ceiling(curr - k); if (tmp != null) { ans = Math.max(ans, curr - tmp); } sumSet.add(curr); } } } return ans; }
873. 最長的斐波那契子序列的長度
與最長遞增子序列類似挂滓，斐波那契子序列需要向前看兩位。
-
樸素的動態(tài)規(guī)劃時間復雜度 O(n^3)啸胧，可通過 HashMap 降低至 O(n^2)杂彭。
public int lenLongestFibSubseq(int[] arr) { int len = arr.length; Map<Integer, Integer> indexMap = new HashMap<>(); for (int i = 0; i < len; i++) { indexMap.put(arr[i], i); } int[][] dp = new int[len][len]; int max = 0; for (int i = 2; i < len; i++) { for (int j = i - 1; j >= 0; j--) { int k = indexMap.getOrDefault(arr[i] - arr[j], -1); if (k >= 0 && k < j) { dp[j][i] = dp[k][j] + 1; max = Math.max(max, dp[j][i] + 2); } } } return max < 3 ? 0 : max; }
1027. 最長等差數(shù)列
-
解題思路同最長遞增子序列墓毒，dp[i][j] 表示以 nums[i] 和 nums[j] 為首尾的等差數(shù)列。
public int longestArithSeqLength(int[] nums) { int[][] dp = new int[nums.length][nums.length]; Map<Integer, Integer> indexMap = new HashMap<>(); int ans = 2; for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { Integer k = indexMap.getOrDefault(2 * nums[i] - nums[j], -1); if (k >= 0 && k < i) { dp[i][j] = Math.max(dp[i][j], dp[k][i] + 1); ans = Math.max(ans, dp[i][j] + 2); } } indexMap.put(nums[i], i); } return ans; }
368. 最大整除子集
排序數(shù)組使得最大整除子集的最大值下標最大亲怠。
-
通過一維數(shù)組存儲整除子集的下標所计。
public List<Integer> largestDivisibleSubset(int[] nums) { Arrays.sort(nums); int[] dp = new int[nums.length]; Arrays.fill(dp, 1); int[] index = new int[nums.length]; for (int i = 0; i < index.length; i++) { index[i] = i; } int maxIndex = 0; for (int i = 1; i < nums.length; i++) { for (int j = i - 1; j >= 0; j--) { if (nums[i] % nums[j] == 0 && dp[i] < dp[j] + 1) { dp[i] = dp[j] + 1; index[i] = j; if (dp[maxIndex] < dp[i]) { maxIndex = i; } } } } List<Integer> result = new ArrayList<>(); for (int i = 0, idx = maxIndex; i < dp[maxIndex]; i++) { result.add(0, nums[idx]); idx = index[idx]; } return result; }
32. 最長有效括號
-
dp[i] 表示 0...i 最長有效括號，dp[i] 根據(jù) s.charAt(i) == ')' 分情況討論团秽。
public int longestValidParentheses(String s) { int[] dp = new int[s.length()]; int maxLen = 0; for (int i = 1; i < s.length(); i++) { if (s.charAt(i) == ')') { if (s.charAt(i - 1) == '(') { dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2; } else { if (i - dp[i - 1] - 1 >= 0 && s.charAt(i - dp[i - 1] - 1) == '(') { dp[i] = dp[i - 1] + 2 + (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0); } } } maxLen = Math.max(maxLen, dp[i]); } return maxLen; } -
此題還可以通過棧解決主胧。
public int longestValidParentheses(String s) { int maxans = 0; Deque<Integer> stack = new LinkedList<Integer>(); stack.push(-1); for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '(') { stack.push(i); } else { stack.pop(); if (stack.isEmpty()) { stack.push(i); } else { maxans = Math.max(maxans, i - stack.peek()); } } } return maxans; }
413. 等差數(shù)列劃分
dp[i] 表示以 num[i] 結尾的子數(shù)組的等差數(shù)列個數(shù)。
-
dp 數(shù)組的和就是所有等差子數(shù)組的個數(shù)习勤。
public int numberOfArithmeticSlices(int[] nums) { int[] dp = new int[nums.length]; int res = 0; for (int i = 2; i < nums.length; i++) { if (2 * nums[i - 1] == nums[i - 2] + nums[i]) { dp[i] = dp[i - 1] + 1; } res += dp[i]; } return res; }
91. 解碼方法
-
遞歸解法會超時踪栋，使用動態(tài)規(guī)劃，dp[i] 表示 s(0...i) 的解碼方法图毕。
public int numDecodings(String s) { if (s == null || s.length() == 0) { return 0; } int[] dp = new int[s.length()]; dp[0] = s.charAt(0) == '0' ? 0 : 1; for (int i = 1; i < s.length(); i++) { if (s.charAt(i) == '0') { if (s.charAt(i - 1) == '1' || s.charAt(i - 1) == '2') { dp[i] = i == 1 ? 1 : dp[i - 2]; } else { return 0; } } else { String subStr = s.substring(i - 1, i + 1); if (subStr.compareTo("10") > 0 && subStr.compareTo("26") <= 0) { dp[i] = dp[i-1] + (i == 1 ? 1 : dp[i - 2]); } else { dp[i] = dp[i - 1]; } } } return dp[s.length() - 1]; }
132. 分割回文串 II
-
先求出所有的回文串dp[i][j]夷都，基于 dp 數(shù)組再求 min[0...i] 最少分割次數(shù)。
public int minCut(String s) { boolean[][] dp = new boolean[s.length()][s.length()]; for (int i = 0; i < s.length(); i++) { dp[i][i] = true; } for (int i = 1; i < s.length(); i++) { for (int j = 0; j < i; j++) { if (s.charAt(i) == s.charAt(j) &&(i - j < 2 || dp[j + 1][i - 1])) { dp[j][i] = true; } } } int[] minNum = new int[s.length()]; for (int i = 0; i < s.length(); i++) { minNum[i] = i; } for (int i = 1; i < s.length(); i++) { for (int j = i - 1; j >= 0; j--) { if (dp[j][i]) { minNum[i] = Math.min(minNum[i], j == 0 ? 0 : minNum[j - 1] + 1); } else { minNum[i] = Math.min(minNum[i], minNum[i - 1] + 1); } } } return minNum[s.length() - 1]; }
單串問題之打家劫舍系列
198.打家劫舍
-
打家劫舍最簡單情形予颤，相鄰單位不能同時偷盜囤官，動態(tài)規(guī)劃方程
dp[i] = max(dp[i - 1], dp[i -2] + nums[i])。public int rob(int[] nums) { if (nums.length < 2) { return nums[0]; } int[] dp = new int[nums.length]; dp[0] = nums[0]; dp[1] = Math.max(nums[0], nums[1]); for (int i = 2; i < nums.length; i++) { dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]); } return dp[nums.length - 1]; }
213.打家劫舍 II
-
所有房子連成環(huán)蛤虐，首尾不能同時偷盜党饮，所以分開考慮。
public int rob(int[] nums) { if (nums.length < 2) { return nums[0]; } return Math.max(rob(nums, 0, nums.length - 2), rob(nums, 1, nums.length - 1)); } public int rob(int[] nums, int start, int end) { if (start == end) { return nums[start]; } int[] dp = new int[nums.length]; dp[start] = nums[start]; dp[start + 1] = Math.max(nums[start], nums[start + 1]); for (int i = start + 2; i <= end; i++) { dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]); } return dp[end]; }
740. 刪除并獲得點數(shù)
選擇一個數(shù)字 num 之后驳庭，對應的相同數(shù)字全部被選擇刑顺。
-
num - 1 和 num + 1 不能被選擇，即打家劫舍的變形饲常，dp[i] 表示數(shù)字 0...i 中能選擇的最大點數(shù)蹲堂。
public int deleteAndEarn(int[] nums) { int maxNum = Arrays.stream(nums).max().getAsInt(); int[] count = new int[maxNum + 1]; for (int num : nums) { count[num]++; } int[] dp = new int[count.length]; dp[0] = 0; dp[1] = count[1]; for (int i = 2; i < count.length; i++) { dp[i] = Math.max(dp[i - 1], dp[i - 2] + count[i] * i); } return dp[count.length - 1]; }
1388.3n 塊披薩
動態(tài)規(guī)劃，與環(huán)裝打家劫舍比較類似贝淤。
-
動態(tài)規(guī)劃方程
dp[i][j]表示在 0 ... i 塊披薩中選 j 塊披薩獲得的價值贯城。public int maxSizeSlices(int[] slices) { if (slices.length <= 3) { return Arrays.stream(slices).max().getAsInt(); } return Math.max(maxSizeSlices(slices, 0, slices.length -2), maxSizeSlices(slices, 1, slices.length - 1)); } public int maxSizeSlices(int[] nums, int start, int end) { int n = nums.length / 3; int[][] dp = new int[nums.length][n + 1]; dp[start][1] = nums[start]; dp[start + 1][1] = Math.max(nums[start], nums[start + 1]); for (int i = start + 2; i <= end; i++) { for (int j = 1; j <= n; j++) { dp[i][j] = Math.max(dp[i - 1][j], dp[i - 2][j - 1] + nums[i]); } } return dp[end][n]; }
單串問題之股票買賣系列
121. 買賣股票的最佳時機
-
只能買賣一次, dp[i][0] 表示第 i 天未持有股票的收益，dp[i][1] 表示第 i 天持有骨片的收益霹娄。
public int maxProfit(int[] prices) { int[][] profits = new int[prices.length][2]; profits[0][1] = - prices[0]; for (int i = 1; i < prices.length; i++) { profits[i][0] = Math.max(profits[i - 1][0], profits[i - 1][1] + prices[i]); profits[i][1] = Math.max(profits[i - 1][1], - prices[i]); } return profits[prices.length - 1][0]; }
122. 買賣股票的最佳時機 II
-
可以進行無數(shù)次買賣能犯，所以計算第 i 天持有股票的收益時，需要考慮第 i - 1 天未持有股票的情況犬耻。
public int maxProfit(int[] prices) { int[][] profits = new int[prices.length][2]; profits[0][1] = - prices[0]; for (int i = 1; i < prices.length; i++) { profits[i][0] = Math.max(profits[i - 1][0], profits[i - 1][1] + prices[i]); profits[i][1] = Math.max(profits[i - 1][1], profits[i - 1][0] - prices[i]); } return profits[prices.length - 1][0]; }
123. 買賣股票的最佳時機 III
最多進行兩次交易踩晶，需要將 dp 數(shù)組擴充到三維，記錄進行了多少次交易枕磁。
-
注意 dp 數(shù)組的初始化渡蜻。
public int maxProfit(int[] prices) { int[][][] profits = new int[prices.length][2][3]; profits[0][1][1] = - prices[0]; profits[0][1][2] = Integer.MIN_VALUE; for (int i = 1; i < prices.length; i++) { for (int j = 2; j >= 1; j--) { profits[i][0][j] = Math.max(profits[i - 1][0][j], profits[i - 1][1][j] + prices[i]); profits[i][1][j] = Math.max(profits[i - 1][1][j], profits[i - 1][0][j - 1] - prices[i]); } } return Arrays.stream(profits[prices.length - 1][0]).max().getAsInt(); }
188. 買賣股票的最佳時機 IV
最多進行 k 次交易，最通用的情況。
當 k > n / 2 時茸苇，變?yōu)闊o限次交易的情況排苍，特殊處理。
public int maxProfit(int k, int[] prices) {
if (k == 0) {
return 0;
}
if (k > prices.length / 2) {
return maxProfit(prices);
}
int[][][] profits = new int[prices.length][2][k + 1];
profits[0][1][1] = - prices[0];
for (int i = 2; i <= k; i++) {
profits[0][1][i] = Integer.MIN_VALUE;
}
for (int i = 1; i < prices.length; i++) {
for (int j = 1; j <= k; j++) {
profits[i][0][j] = Math.max(profits[i - 1][0][j], profits[i - 1][1][j] + prices[i]);
profits[i][1][j] = Math.max(profits[i - 1][1][j], profits[i - 1][0][j - 1] - prices[i]);
}
}
return Arrays.stream(profits[prices.length - 1][0]).max().getAsInt();
}
public int maxProfit(int[] prices) {
if (prices.length == 0) {
return 0;
}
int[][] profits = new int[prices.length][2];
profits[0][1] = - prices[0];
for (int i = 1; i < prices.length; i++) {
profits[i][0] = Math.max(profits[i - 1][0], profits[i - 1][1] + prices[i]);
profits[i][1] = Math.max(profits[i - 1][1], profits[i - 1][0] - prices[i]);
}
return profits[prices.length - 1][0];
}
309. 最佳買賣股票時機含冷凍期
-
冷凍期即表示計算 dp[i] 時学密，需要向前看一天淘衙。
public int maxProfit(int[] prices) { if (prices.length == 0) { return 0; } int[][] profits = new int[prices.length][2]; profits[0][1] = - prices[0]; for (int i = 1; i < prices.length; i++) { profits[i][0] = Math.max(profits[i - 1][0], profits[i - 1][1] + prices[i]); profits[i][1] = Math.max(profits[i - 1][1], (i == 1 ? 0 : profits[i - 2][0]) - prices[i]); } return profits[prices.length - 1][0]; }
714. 買賣股票的最佳時機含手續(xù)費
-
賣掉股票的時候減掉手術費。
public int maxProfit(int[] prices, int fee) { if (prices.length == 0) { return 0; } int[][] profits = new int[prices.length][2]; profits[0][1] = - prices[0]; for (int i = 1; i < prices.length; i++) { profits[i][0] = Math.max(profits[i - 1][0], profits[i - 1][1] + prices[i] - fee); profits[i][1] = Math.max(profits[i - 1][1], profits[i - 1][0] - prices[i]); } return profits[prices.length - 1][0]; }
雙串問題
1143.最長公共子序列
-
關鍵在于構造動態(tài)規(guī)劃方程腻暮。
dp[i][j] = 最長公共子序列 { text1[0 : i], text2[0 : j]}public int longestCommonSubsequence(String text1, String text2) { int len1 = text1.length(); int len2 = text2.length(); int[][] dp = new int[len1 + 1][len2 + 1]; for (int i = 1; i <= len1; i++) { for (int j = 1; j <= len2; j++) { if (text1.charAt(i - 1) == text2.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[len1][len2]; }
1713.得到子序列的最少操作次數(shù)
-
由于
target中元素互不相同彤守，故將arr數(shù)組映射到target數(shù)組元素坐標上，將問題轉化為求兩個映射下標數(shù)組的最長公共子序列哭靖， 而target映射下標數(shù)組是嚴格遞增的具垫，進一步將問題轉化為求arr映射的下標數(shù)組最長遞增子序列問題。public int minOperations(int[] target, int[] arr) { HashMap<Integer, Integer> index = new HashMap<>(); for (int i = 0; i < target.length; i++) { index.put(target[i], i); } int[] dp = new int[arr.length]; int maxLen = 0; for (int num: arr) { Integer numIndex = index.get(num); if (numIndex != null) { int l = 0, r = maxLen; while (l < r) { int m = l + (r - l) / 2; if (dp[m] < numIndex) { l = m + 1; } else { r = m; } } dp[l] = numIndex; if (r == maxLen) { maxLen++; } } } return target.length - maxLen; }
動態(tài)規(guī)劃方程難度 ??????????
887.雞蛋掉落
方程比較難想出來
樸素的動態(tài)規(guī)劃會超時试幽，需要借助二分查找優(yōu)化時間復雜度筝蚕。
-
二分查找的思想來自于單調直線函數(shù)“谷底”極值。
public int superEggDrop(int k, int n) { int[][] dp = new int[n+ 1][k + 1]; for (int i = 1; i <= n; i++) { Arrays.fill(dp[i], i); } for (int i = 2; i <= n; i++) { for (int j = 2; j <= k; j++) { int lo = 1, hi = i; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (dp[mid - 1][j - 1] < dp[i - mid][j]) { lo = mid + 1; } else { hi = mid; } } dp[i][j] = Math.max(dp[lo - 1][j - 1], dp[i - lo][j]) + 1; } } return dp[n][k]; }
