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

完结撒花