Leetcode百題斬-DP

又到了最好玩的dp了，各種玄學轉移也算是其樂無窮。前段時間剛做的LCA正是這種題的小試牛刀，如果當時就把這個專題刷完了，或許我現在已經從西溪園區跑到云谷園區了。

不過，恐怖如斯的dp專題居然只給了一道hard，基本也沒啥難度可言了。看部分題目之前也刷過，但也沒怎么記錄在博客里，這次統一再刷一遍，快速過掉。部分題深挖一下倒也可以溫習一些旁路的知識點

二維

先看二維，理論上二維要比一維要好想一點

5. Longest Palindromic Substring[Medium]

思路：這題就是之前通義實驗室出的面試題，雖然有dp做法，但中心擴散法和終極Manachar算法還是挺有趣的。由于是幾個月前剛做的，這里就不贅述了，感興趣可以往前翻

多學一點：馬拉車算法

最長回文子序列-CSDN博客

64. Minimum Path Sum[Medium]

思路：求矩陣左上到右下的最小路徑和，這種矩陣的求和是最經典的dp了，直接左上兩格轉移即可

/*
Author Owen_Q
*/
public class MinimumPathSum {public static int minPathSum(int[][] grid) {int m = grid.length;int n = grid[0].length;int[][] dp = new int[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (i == 0 && j == 0) {dp[i][j] = grid[i][j];} else if (i == 0) {dp[i][j] = dp[i][j - 1] + grid[i][j];} else if (j == 0) {dp[i][j] = dp[i - 1][j] + grid[i][j];} else {dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];}}}return dp[m - 1][n - 1];}
}

72. Edit Distance[Medium]

思路：單詞變更和矩陣題類似，也十分容易出dp類型的題，以新舊兩個單詞的長度作為dp維度，每次變更一位進行轉移，那么增，刪，改分別剛好對應了左，上和左上三個轉移區域。針對改特判一下若尾部相同則可以不進行修改即可。

/*
Author Owen_Q
*/
public class WordsDistance {public static int minDistance(String word1, String word2) {int m = word1.length();int n = word2.length();int[][] dp = new int[m + 1][n + 1];for (int i = 0; i <= m; i++) {for (int j = 0; j <= n; j++) {if (i == 0) {dp[i][j] = j;} else if (j == 0) {dp[i][j] = i;} else {dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1]);if (word1.charAt(i - 1) == word2.charAt(j - 1)) {dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i][j]);} else {dp[i][j] = Math.min(dp[i - 1][j - 1] + 1, dp[i][j]);}}}}return dp[m][n];}
}

1143. Longest Common Subsequence[Medium]

思路：經典二維dp問題，LCS，話不多說直接上代碼

/*
Author Owen_Q
*/
public class LongestCommonSequence {public static int longestCommonSubsequence(String text1, String text2) {int n = text1.length();int m = text2.length();int[][] dp = new int[n + 1][m + 1];for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; 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[n][m];}
}

?118. Pascal's Triangle[Easy]

思路：楊輝三角來咯

/*
Author Owen_Q
*/
public class PascalTriangle {public static List<List<Integer>> generate(int numRows) {List<List<Integer>> result = new ArrayList<>();int[][] dp = new int[numRows][numRows];for (int i = 0; i < numRows; i++) {List<Integer> rowResult = new ArrayList<>();for (int j = 0; j <= i; j++) {if (j == 0 || j == i) {dp[i][j] = 1;} else {dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];}rowResult.add(dp[i][j]);}result.add(rowResult);}return result;}
}

多學一點：組合數性質

比較有意思的就是，楊輝三角的值剛好對應了組合數的值，即楊輝三角的第n行第m列剛好是組合數的? $c_{n}^{m}=\frac{n!}{m!\times (n-m)!}$ 。這剛好對應了組合數的性質，即 $c_{n}^{m} = c_{n-1}^{m} +c_{n-1}^{m-1}$ 。此外，楊輝三角的每一行也剛好就是? $(a+b)^{n}$ ?二項展開式中的系數

62. Unique Paths[Medium]

思路：求矩陣左上到右下的路徑數量，和上述編號64題極其類似，上面是求最小最小值，這里是求和，換湯不換藥

/*
Author Owen_Q
*/
public class UniquePaths {public static int uniquePaths(int m, int n) {int[][] dp = new int[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (i == 0 && j == 0) {dp[i][j] = 1;} else if (i == 0) {dp[i][j] = dp[i][j - 1];} else if (j == 0) {dp[i][j] = dp[i - 1][j];} else {dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}}return dp[m - 1][n - 1];}
}

一維?

接下來看看一維，其實一維也很簡單，leetcode真的很良心了，基本毫無難度

152. Maximum Product Subarray[Medium]

思路：求數串的最大子串乘積，其實可以不用dp，在不考慮符號的情況下，乘積肯定是越乘越大，考慮符號，那么記錄一下當前最大乘積和最小乘積，每次遇到零則清空一下即可。最后注意一下單個數字的場景，這種情況下該數字即為最大乘積，而非初始化的0，特判一下即可；

/*
Author Owen_Q
*/
public class MaximumProductSubarray {public static void main(String[] args) {System.out.println(maxProduct(new int[] {2, 3, -2, 4}));System.out.println(maxProduct(new int[] {-2, 0, -1}));System.out.println(maxProduct(new int[] {-2}));System.out.println(maxProduct(new int[] {-4, -3, -2}));}public static int maxProduct(int[] nums) {if (nums.length == 1) {return nums[0];}int result = nums[0];int curMaxProduct = 0;int curMinProduct = 0;for (int num : nums) {if (num == 0) {curMaxProduct = 0;curMinProduct = 0;} else if (num > 0) {curMaxProduct = Math.max(curMaxProduct * num, num);curMinProduct = Math.min(curMinProduct * num, num);} else {int preMaxProduct = curMaxProduct;curMaxProduct = Math.max(curMinProduct * num, num);curMinProduct = Math.min(preMaxProduct * num, num);}//System.out.println(num + "*" + curMaxProduct + "*" + curMinProduct);result = Math.max(result, curMaxProduct);}return result;}
}

279. Perfect Squares[Medium]

思路：給定某個數，求當前數最少可以由多少個完全平方數求和而來。那么這個dp思路也很好想，每個數由其減去一個完全平方數轉移而來，即? $dp[i] = min(dp[i-k^{2}]+1), k^{2} <= i$

/*
Author Owen_Q
*/
public class PerfectSquares {public static int numSquares(int n) {int[] dp = new int[n + 1];for (int i = 0; i <= n; i++) {dp[i] = i;for (int j = 1; j * j <= i; j++) {dp[i] = Math.min(dp[i], dp[i - j * j] + 1);}}return dp[n];}
}

多學一點：四平方和定理

上述遞推的時間復雜度為 $O(n\sqrt{n})$ ，對于大數會有很大的消耗。因此如果有數學方法進行優化，那將大大降低時間復雜度。這里我們引入拉格朗日的四平方數定理的，即：任何一個正整數都可以表示為至多四個正整數的平方和。這個定理一下就把這題的值域縮小到了? $[1,4]$ ，這四個整數內。進一步了解，在四平方和定理的基礎上，還有一個更嚴格的定理，就是勒讓德的三平方和定理，即：當且僅當? $n= 4^{k}\times (8m+7)$ ?時，n可以被表示為四個正整數的平方。那么，當? $n\neq 4^{k}\times (8m+7)$ ?時，答案的數量又被縮小到? $[1,3]$ 。于是直接特判即可。針對答案為1的場景，n為完全平方式。針對答案為2的場景， $n=a^{2}+b^{2}$ ，那么枚舉 $a$ ，如果? $b=n-a^{2}$ ?為完全平方數，則成立。最后，若1和2均不滿足，則答案為3。于是，利用平方定理，最大的時間耗時就是在判斷答案是否為2這條分支上，于是整體的時間復雜度就被降到了 $O(\sqrt{n})$

/*
Author Owen_Q
*/
public class PerfectSquares {public static int numSquaresWithMaths(int n) {if (foutSquares(n)) {return 4;}if (perfectSquares(n)) {return 1;}if (twoSquares(n)) {return 2;}return 3;}private static boolean foutSquares(int n) {while (n % 4 == 0) {n /= 4;}return n % 8 == 7;}private static boolean perfectSquares(int n) {int sqrtn = (int)Math.sqrt(n);return sqrtn * sqrtn == n;}private static boolean twoSquares(int n) {for (int i = 1; i * i < n; i++) {if (perfectSquares(n - i * i)) {return true;}}return false;}
}

直接登頂

70. Climbing Stairs[Easy]

思路：不愧是easy題，斐波那契數組和楊輝三角堪稱dp屆的始祖。這題就是斐波那契數組，直接求

/*
Author Owen_Q
*/
public class ClimbingStairs {public static int climbStairs(int n) {int[] dp = new int[n + 1];dp[0] = 1;dp[1] = 1;for (int i = 2; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
}

多學一點：矩陣快速冪

一提到斐波那契，怎么能沒有矩陣快速冪。

基礎遞推01-CSDN博客

首先，觀察通項公式

$dp[n] = dp[n-1]+dp[n-2]$

將通項公式轉化到矩陣中，可以得到矩陣的遞推關系

$\begin{bmatrix} dp[n]\\ dp[n-1] \end{bmatrix}=\begin{bmatrix} dp[n-1]+dp[n-2]\\ dp[n-1] \end{bmatrix}=\begin{bmatrix} 1\times dp[n-1]+1\times dp[n-2]\\ 1\times dp[n-1] + 0\times dp[n-2] \end{bmatrix}=\begin{bmatrix} 1& 1\\ 1 & 0 \end{bmatrix}\begin{bmatrix} dp[n-1]\\ dp[n-2] \end{bmatrix}=\begin{bmatrix} 1& 1\\ 1 & 0 \end{bmatrix}^{k}\begin{bmatrix} dp[n-k]\\ dp[n-k-1] \end{bmatrix} =\begin{bmatrix} 1& 1\\ 1 & 0 \end{bmatrix}^{n-1}\begin{bmatrix} dp[1]\\ dp[0] \end{bmatrix}$

于是， $O(n)$ ?的遞推線性復雜度就被降為了? $O(logn)$ ?的求矩陣冪的復雜度

/*
Author Owen_Q
*/
public class ClimbingStairs {public static int climbStairsWithBinaryExponentiation(int n) {int[][] a = {{1, 1}, {1, 0}};return power(a, n)[0][0];}private static int[][] power(int[][] a, int n) {if (a == null) {return null;}int len = a.length;int size = a[0].length;if (len != size) {return null;}int[][] result = {{1, 0}, {0, 1}};while (n > 0) {if ((n & 1) == 1) {result = multiple(result, a);}a = multiple(a, a);n >>= 1;}return result;}private static int[][] multiple(int[][] a, int[][] b) {int alen = a.length;int blen = b.length;int asize = a[0].length;int bsize = b[0].length;if (asize != blen) {return null;}int c[][] = new int[alen][bsize];for (int i = 0; i < alen; i++) {for (int j = 0; j < bsize; j++) {c[i][j] = 0;for (int k = 0; k < asize; k++) {c[i][j] += a[i][k] * b[k][j];}}}return c;}
}

再衍生一步，其實任何線性其次遞推公式都可以用矩陣快速冪來優化

針對 $m$ 項遞推? $f(n)=\sum_{i=1}^{m}a_{i}\times f(n-i)$ ?，都可以構造 $m \times m$ 的矩陣 $\begin{bmatrix} a_{1}& a_{2}& a_{3}& ...& a_{m-1}& a_{m}\\ 1& 0 & 0 & ... & 0 & 0\\ 0& 1& 0 &... &0 &0 \\ 0& 0 & 1 & ... & 0 & 0\\ ...& ... & ... & ... & ... & ...\\ 0& 0 &0 &... & 1 & 0 \end{bmatrix}$

然后即可基于矩陣快速冪進行計算，而對應的單位矩陣即為

$\begin{bmatrix} 1& 0 & 0 & ... & 0\\ 0& 1& 0 &... &0 \\ 0& 0 & 1 & ... & 0\\ ...& ... & ... & ... & ...\\ 0& 0 &0 &... & 1 \end{bmatrix}$

198. House Robber[Medium]

思路：選物品，每個物品有一定價值，不占容量，但不可連續選擇，求最大物品數。這像是個低配版背包，直接相鄰轉移即可

/*
Author Owen_Q
*/
public class HorseRobber {public static int rob(int[] nums) {int n = nums.length;int[] dp = new int[n + 1];dp[0] = 0;dp[1] = nums[0];for (int i = 2; i <= n; i++) {dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);}return dp[n];}
}

300. Longest Increasing Subsequence[Medium]

思路：經典LIS問題，最長單增子序列，不多說直接求

/*
Author Owen_Q
*/
public class LongestIncreasingSubsequence {public static int lengthOfLIS(int[] nums) {int n = nums.length;int[] dp = new int[n];dp[0] = 1;int re = 1;for (int i = 1; i < n; i++) {dp[i] = 1;for (int j = 0; j < i; j++) {if (nums[j] < nums[i]) {dp[i] = Math.max(dp[i], dp[j] + 1);}}re = Math.max(dp[i], re);}return re;}
}

多學一點：貪心?

這么經典的問題，當然不能用DP，這平方級別的復雜度，當然要想著優化一下。

這里用到一個神奇的思路，就是轉換狀態和狀態值

原先? $dp[i]$ ?表示結尾為? $num[i]$ ?的最長單增子序列的長度

那么這次引入新的數組? $g[i]$ ?表示長度為? $i$ ?的最長單增子序列的最小結尾值。

不難發現， $g[i]$ ?一定是單增的。比如，某長度為i的最長公共子序列，最后一位為? $g[i]$ ?刪去最后一位后，倒數第二位一定大于等于? $g[i-1]$ ，因為若倒數第二位小于? $g[i-1]$ ，那么這個數自身就可以更新? $g[i-1]$ ?使得值更小。于是這題就變成了貪心求? $g[i]$ 。

具體貪心的過程即是，遍歷數組，針對每個新的數，找到g數組中大于當前數的首個位置，若沒有找到，則將當前數塞到g數組末尾。否則，更新找到的位置為當前數。至于找到首個大于當前數的位置，可以直接用二分來實現，最終能將時間內復雜度降到? $O(nlogn)$ 。

下面來說一下二分搜索。java中有現成的函數 java.util.Collections#binarySearch(java.util.List<? extends java.lang.Comparable<? super T>>, T)，要求傳入的數組一定為有序的。返回值分為兩種，若為正數，則說明當前值已找到，返回的結果即為當前值在數組中的位置。若返回值為負數，則表示當前值未找到，返回的結果為當前值可插入的位置-1

/*
Author Owen_Q
*/
public class LongestIncreasingSubsequence {public static int lengthOfLISGreedy(int[] nums) {List<Integer> g = new ArrayList<>();for (int num : nums) {int searchResult = Collections.binarySearch(g, num);if (searchResult < 0) {searchResult = searchResult * -1 - 1;if (searchResult == g.size()) {g.add(num);} else {g.set(searchResult, num);}}}return g.size();}
}

效果拔群?

322. Coin Change[Medium]

思路：提到DP，怎么能沒有背包呢！典型的背包問題，由于硬幣的數量無限，那么這就是個完全背包問題，轉移時從小向大遍歷。如果這題每種硬幣只能取一個，那就變成了最基礎的01背包問題，從大向小遍歷即可。背包做完舒服了

/*
Author Owen_Q
*/
public class CoinChange {public static int coinChange(int[] coins, int amount) {int[] dp = new int[amount + 1];Arrays.fill(dp, -1);dp[0] = 0;for (int coin : coins) {for (int i = 1; i <= amount; i++) {if (i >= coin && dp[i - coin] >= 0) {if (dp[i] == -1) {dp[i] = dp[i - coin] + 1;} else {dp[i] = Math.min(dp[i], dp[i - coin] + 1);}}}}return dp[amount];}
}

416. Partition Equal Subset Sum[Medium]

思路：給定一個數組，求能否將數組中的數均勻分成兩塊。由于數組中的數字不可分，那么又可以轉換為背包問題。每個數均只有一個，可以用01背包。這題由于只需要求可行性，因此，直接將初始dp默認為1，別的均初始化為0，然后設置背包容量為數組和的一半，通過最大值進行轉移看最終能否將1轉移到半背包容量的位置處

/*
Author Owen_Q
*/
public class PartitionEqualSubsetSum {public static boolean canPartition(int[] nums) {int sum = 0;for (int num : nums) {sum += num;}if (sum % 2 == 1) {return false;}sum >>= 1;int[] dp = new int[sum + 1];dp[0] = 1;for (int num : nums) {for (int i = sum; i >= num; i--) {dp[i] = Math.max(dp[i], dp[i - num]);}}return dp[sum] == 1;}
}

139. Word Break[Medium]

思路：判斷某個字符串是否可以被分割為多個特定字典中的單詞。當然想到dp，表示當前位置為止的前綴是否滿足要求。轉移方程就是往前遍歷，找到前面滿足的位置，再判斷從找到的位置到當前位置中的字符串是否能在字典中尋找到，即? $dp[i]=dp[j]\wedge word[j,i)$

/*
Author Owen_Q
*/
public class WordBreak {public static boolean wordBreak(String s, List<String> wordDict) {int len = s.length();boolean[] dp = new boolean[len + 1];dp[0] = true;for (int i = 1; i <= len; i++) {for (int j = 0; j < i; j++) {if (wordDict.contains(s.substring(j, i)) && dp[j]) {dp[i] = true;break;}}}return dp[len];}
}

多學一點：字典樹（Trie）

不難發現dp轉移過程中，有很多無用的轉移，比如當當前字典中沒有以當前字母為開頭的字段時，就可以停止這輪轉移。甚至更進一步，當當前字典中沒有以當前搜索的區域為前綴的字段時，就可以停止繼續搜索了。

還記得之前特地有個專題說到了前綴問題的數據結構字典樹嗎，這不就用上了

Leetcode百題斬-字典樹_leetcode 字典樹-CSDN博客

于是開始搜索，搜索時為了避免重復搜索，可以使用記憶化搜索，確保每輪只要搜索一次。

與之前動態轉移從前往后判斷，用? $dp$ ?來記錄前綴是否滿足條件不同，這次我們從后往前判斷，并? $dp$ ?我們用來記錄后綴是否滿足條件。

搜索分三部分：特判，搜索找到后進行遞歸搜索以及搜索沒找到時的遍歷搜索

第一部分是特判。每次搜索，特判若首字母不在字典樹中則直接返回失敗，若整個字符串在字典樹中被搜到則直接返回成功。

第二部分是遞歸搜索。從頭開始尋找字典樹中的字段位置，若搜索到，則以當前位置進行遞歸向后搜索。

第三部分是遍歷搜索。當然若沒搜索到，則將當前搜索點向后順移一位判斷被延長后的子串是否在字典樹中，并繼續搜索

/*
Author Owen_Q
*/
public class WordBreak {public static boolean wordBreakTrie(String s, List<String> wordDict) {int len = s.length();int[] dp = new int[len];Trie trie = new Trie();for (String word : wordDict) {trie.insert(word);}return wordBreakTrieSearch(s, trie, 0, dp);}private static boolean wordBreakTrieSearch(String s, Trie trie, int pos, int[] dp) {int len = s.length();if (dp[pos] != 0) {return dp[pos] == 1;}if (!trie.startsWith(String.valueOf(s.charAt(pos)))) {dp[pos] = -1;return false;}if (trie.search(s.substring(pos))) {dp[pos] = 1;return true;}for (int i = pos + 1; i < len; i++) {if (trie.search(s.substring(pos, i)) && wordBreakTrieSearch(s, trie, i, dp)) {dp[pos] = 1;return true;}if (!trie.startsWith(s.substring(pos, i + 1))) {dp[pos] = -1;return false;}}dp[pos] = -1;return false;}
}

效果還是挺明顯的

32. Longest Valid Parentheses[Hard]

思路：作為dp專題唯一的hard，倒是要好好來看一下。

括號匹配，求最長合法括號串。

由于合法括號串一定是以? $)$ ?結尾，因此所有? $($ ?處的值一定為0。

接下來開始考慮轉移。

一共有兩種轉移方案，剛好對應了括號串的兩種合法狀態

一是 $...()$

若當前位的前一位為? $($ ，則可以直接形成匹配，長度無腦加2

二是 $...((...))$

若當前位的前一位為? $)$ ，則需要判斷前一位是否形成合法串了。如果形成了合法串，則需要再向前找到前一位合法串前的位是否為? $($ ，即是否可以再前一個合法串外圍再包一個匹配。

此外還需要再注意的一點就是，如果外圍匹配成功，則需要再向前往一位，再加一個前位的合法串長度。因為你多一個匹配很有可能將兩個合法串連接到了一起

/*
Author Owen_Q
*/
public class LongestValidParentheses {public static int longestValidParentheses(String s) {int len = s.length();int[] dp = new int[len + 1];int maxLen = 0;for (int i = 0; i < len; i++) {if (s.charAt(i) == '(') {continue;}if (i > 0 && s.charAt(i - 1) == '(') {dp[i + 1] = dp[i - 1] + 2;maxLen = Math.max(maxLen, dp[i + 1]);} else if (i - dp[i] > 0 && s.charAt(i - dp[i] - 1) == '(') {dp[i + 1] = dp[i] + 2;if (i - dp[i] - 1 > 0) {dp[i + 1] += dp[i - dp[i] - 1];}maxLen = Math.max(maxLen, dp[i + 1]);}}return maxLen;}}

多學一點：貪心

回歸傳統思維，直接貪心模擬。實時記錄當前左右括號的數量，當右括號數量多于左括號時，那么前面的一定無法組成合法場景，直接從頭開始計算。當左右括號數量相等時，統計此時的模擬長度。但這種場景其實針對最終左括號多于右括號的場景無法得出，因為不知道最右邊的右括號匹配到了哪個左括號，即有效的長度究竟是多少。那么最簡單的方式就是反過來再求一次就好了

/*
Author Owen_Q
*/
public class LongestValidParentheses {public static int longestValidParenthesesGreedy(String s) {int sLen = s.length();int left = 0;int right = 0;int len = 0;int maxLen = 0;for (int i = 0; i < sLen; i++) {len++;if (s.charAt(i) == '(') {left++;} else {right++;}if (right > left) {left = 0;right = 0;len = 0;}if (left == right) {maxLen = Math.max(maxLen, len);}}left = 0;right = 0;len = 0;for (int i = sLen - 1; i >= 0; i--) {len++;if (s.charAt(i) == '(') {left++;} else {right++;}if (right < left) {left = 0;right = 0;len = 0;}if (left == right) {maxLen = Math.max(maxLen, len);}}return maxLen;}}

多學一點：棧

其實針對左括號比右括號多無法定位到具體位置的問題，用棧就可以很好的解決。棧可以實時獲取到當前合法串的長度。我們只要把棧底元素始終放置此輪合法的起點，即左括號不比右括號少的首個位置。然后每次左括號位置進棧，右括號位置出棧。那么此輪出棧的元素一定都是合法串的一部分，于是我們只需要在每次出棧的時候，比較當前位置與棧頂位置的差值，即從棧頂到當前一共有多少個元素在棧外，即可獲取到當前串的長度。最后，針對左括號少于右括號的場景，把棧底元素出棧后，再將當前元素入棧，即可確保起點也被成功更新，開啟新的一輪

/*
Author Owen_Q
*/
public class LongestValidParentheses {public static int longestValidParenthesesStack(String s) {Stack<Integer> stack = new Stack<>();stack.push(-1);int len = s.length();int maxLen = 0;for (int i = 0; i < len; i++) {if (s.charAt(i) == '(') {stack.push(i);} else {stack.pop();if (stack.isEmpty()) {stack.push(i);} else {int top = stack.peek();maxLen = Math.max(maxLen, i - top);}}}return maxLen;}}

完結撒花