Loading... # 最长公共子序列（LCS） 定义 dp[i][j] 为 text1[0..i-1]和text2[0..j-1]的最大公共子序列，那么有转移方程如下： $$ \text{dp}[i][j] = \begin{cases} \text{dp}[i-1][j-1] + 1, & \text{if } text1[i-1] == text2[j-1] \\ \max(\text{dp}[i-1][j],\ \text{dp}[i][j-1]), & \text{otherwise} \end{cases} $$ 其实这个也非常的好理解，因为只有 text1[i-1] == text2[j-1] 的时候才能对答案做贡献，所以第一条方程就出来了，而第二条就是因为没有办法做贡献，只能在之前的部分中取一个最大的值。 于是得到代码如下： ```go func longestCommonSubsequence(text1 string, text2 string) int { n := len(text1) m := len(text2) dp := make([][]int, n+1) for i := 0; i <= n; i++ { dp[i] = make([]int, m+1) } for j := 1; j <= m; j++ { for i := 1; i <= n; i++ { if text1[i-1] == text2[j-1] { dp[i][j] = dp[i-1][j-1] + 1 } else { dp[i][j] = max(dp[i-1][j], dp[i][j-1]) } } } return dp[n][m] } ``` 可以看到方程只依赖三个变量 dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]，所以可以优化成一维 dp 数组，依赖项分别是当前格的左斜上，上，左方的值，左斜上需要另外用一个变量存储，然后按行或者按列进行刷新即可。 ```go func longestCommonSubsequence(text1 string, text2 string) int { n := len(text1) m := len(text2) dp := make([]int, m+1) for i := 1; i <= n; i++ { prev := 0 for j := 1; j <= m; j++ { // 保存上一轮的 dp[i-1][j-1] tmp := dp[j] if text1[i-1] == text2[j-1] { dp[j] = prev + 1 } else { dp[j] = max(dp[j], dp[j-1]) } prev = tmp } } return dp[m] } ``` # 最长重复子数组 这个题目和最长公共子序列极其类似以至于我一开始就直接套了LCS的模板，后来发现不对，这个是求子序列的方法，但其实子序列和子数组的解法极其相似，就是一个可以断开，一个不能断开，且公共子数组的最大长度需要通过从局部最优找到全局最优。 ```go func findLength(nums1 []int, nums2 []int) int { n := len(nums1) m := len(nums2) dp := make([][]int, n+1) for i := range dp { dp[i] = make([]int, m+1) } maxLen := 0 for i := 1; i <= n; i++ { for j := 1; j <= m; j++ { if nums1[i-1] == nums2[j-1] { dp[i][j] = dp[i-1][j-1] + 1 maxLen = max(maxLen, dp[i][j]) } else { dp[i][j] = 0 } } } return maxLen } ``` 优化到一维 dp ```go func findLength(nums1 []int, nums2 []int) int { n := len(nums1) m := len(nums2) dp := make([]int, m+1) maxLen := 0 for i := 1; i <= n; i++ { prev := 0 for j := 1; j <= m; j++ { tmp := dp[j] if nums1[i-1] == nums2[j-1] { dp[j] = prev + 1 maxLen = max(maxLen, dp[j]) } else { dp[j] = 0 } prev = tmp } } return maxLen } ``` # 最长递增子序列（LIS） 这道题主要是想不到如何积累结果，因为需要两个数互相比较才能积累。 定义 dp[i] 为以 i 结尾的最长递增子序列，那么我们可以得到 $dp[i] = max(dp[i], dp[j] + 1), 0 <= j < i < n, nums[j] < nums[i]$ ```go func lengthOfLIS(nums []int) int { n := len(nums) dp := make([]int, n) for i := range dp { dp[i] = 1 } res := 1 for i := 1; i < n; i++ { for j := 0; j < i; j++ { if nums[j] < nums[i] { dp[i] = max(dp[i], dp[j]+1) res = max(res, dp[i]) } } } return res } ``` 还有一种贪心算法，维护一个数组，保障里面的数字是严格递增的，一旦出现更小的值则在数组中找到对应的位置替换进去（二分），这样最终遍历得到的便是最长递增子序列的长度，这个数组的定义是长度为i+1的递增子序列中结尾最小的那个值。 ```go func lengthOfLIS(nums []int) int { tails := []int{} for _, num := range nums { l, r := 0, len(tails) for l < r { mid := l + ((r - l) >> 1) if tails[mid] < num { l = mid+1 } else { r = mid } } if l == len(tails) { tails = append(tails, num) } else { tails[l] = num } } return len(tails) } ``` # 最大子数组和 记得原来还在大学的算法课上看到过这道题，结果轮到自己做又不会做了，尝试定义dp二维数组求出每一个子数组和，但是会爆内存，于是降维到一维，定义 `dp[i]` 为 nums[0..i] 的最大子数组和，结果这个定义发现推不出来，卡住了，后面只能看答案，发现定义应该是以 i 结尾的最大子数组和才对，以这个定义就能得到推导公式如下： $dp[i]=max(dp[i-1]+nums[i],nums[i])$ 这个公式粗看可能还会带点疑惑，为啥这一定能保障是最大子数组和，首先我们要知道定义是以 i 结尾的最大子数组和，那么如果 dp[i-1] 都小于 0 了，那必然对我这个以 i 结尾的子数组是负贡献的，所以这个时候取 nums[i] 便是最优结果，当然，这是以 i 结尾的子数组的最大值，并不是全局最优，所以我们还需要定义一个 res 在每一轮循环中更新最大值，进而得到全局最优的子数组和。 ```go func maxSubArray(nums []int) int { n := len(nums) res := nums[0] dp := make([]int, n) // dp[i] 是以 nums[i] 为结尾的最大子数组和 dp[0] = nums[0] for i := 1; i < n; i++ { dp[i] = max(dp[i-1]+nums[i], nums[i]) res = max(res, dp[i]) } return res } ``` 从公式的推演我们可以看到，dp[i] 只依赖于 dp[i-1] 和 nums[i]，那么我们可以优化空间为 O(1)。 ```go func maxSubArray(nums []int) int { n := len(nums) res := nums[0] prev := nums[0] for i := 1; i < n; i++ { cur := max(prev+nums[i], nums[i]) prev = cur res = max(res, cur) } return res } ``` # 最长连续递增序列 这道题跟LIS很相似，但是它需要连续，只要不连续就不算了，所以直接初始化 dp[i] = 1，然后从头到尾扫描一遍，如果满足 nums[i] > nums[i-1] 就 dp[i] = dp[i-1] + 1。 所以甚至可以优化到用一个变量来完成这道题目。 ```go func findLengthOfLCIS(nums []int) int { n := len(nums) dp := make([]int, n) for i := range dp { dp[i] = 1 } res := 1 for i := 1; i < n; i++ { if nums[i] > nums[i-1] { dp[i] = dp[i-1]+1 res = max(res, dp[i]) } } return res } ``` # 最长递增子序列的个数 这道题相当于是在 LIS 上面拓展，需要在 LIS 题目的基础上增加一个 cnt 数组统计以 nums[i] 结尾的递增子序列的个数，然后最后遍历一遍就能得到最长的长度和对应的个数了。 ```go func findNumberOfLIS(nums []int) int { n := len(nums) // 以nums[i]结尾的递增子序列长度 dp := make([]int, n) // 以nums[i]结尾的递增子序列数量 cnt := make([]int, n) for i := 0; i < n; i++ { dp[i] = 1 cnt[i] = 1 } for i := 1; i < n; i++ { for j := 0; j < i; j++ { if nums[j] < nums[i] { if dp[j]+1 > dp[i] { dp[i] = dp[j]+1 cnt[i] = cnt[j] } else if dp[j]+1 == dp[i] { cnt[i] += cnt[j] } } } } maxLen := 0 res := 0 for i := 0; i < n; i++ { if dp[i] > maxLen { maxLen = dp[i] res = cnt[i] } else if dp[i] == maxLen { res += cnt[i] } } return res } ``` Last modification：July 20, 2025 © Allow specification reprint Support Appreciate the author AliPayWeChat Like 如果觉得我的文章对你有用，请随意赞赏
