1. 动态规划在子序列问题中的应用概述动态规划Dynamic Programming是解决子序列问题的利器尤其擅长处理那些需要全局最优解的序列匹配问题。在算法领域子序列问题通常分为两大类连续子序列和非连续子序列。连续子序列要求元素在原序列中必须相邻而非连续子序列则允许元素之间存在间隔。动态规划解决这类问题的核心思想在于状态转移——通过定义合适的状态表示找出当前状态与之前状态之间的关系从而避免重复计算。对于子序列问题我们通常会定义dp[i]或dp[i][j]来表示以第i个元素结尾或考虑前i个元素时的某种最优解。2. 最长递增子序列问题解析300题2.1 问题定义与基本思路最长递增子序列Longest Increasing Subsequence, LIS问题要求在一个无序的整数序列中找到一个子序列使得这个子序列的元素严格递增并且这个子序列的长度尽可能长。这里的子序列不要求连续但必须保持原始顺序。例如对于序列[10,9,2,5,3,7,101,18]最长的递增子序列是[2,3,7,101]长度为4。2.2 动态规划解法详解2.2.1 DP数组定义我们定义dp[i]为以nums[i]结尾的最长递增子序列的长度。这个定义很关键它保证了我们只需要关注以当前元素结尾的情况而不用考虑全局。2.2.2 状态转移方程对于每个i我们需要检查所有j i的元素if nums[i] nums[j]: dp[i] max(dp[i], dp[j] 1)这个方程的含义是如果当前数字nums[i]比前面的某个数字nums[j]大那么我们可以把nums[i]接在以nums[j]结尾的子序列后面形成一个新的更长的子序列。2.2.3 初始化与遍历顺序每个dp[i]至少为1只包含自己所以初始化为全1数组。遍历顺序是外层循环i从1到n-1内层循环j从0到i-1。2.2.4 完整代码实现class Solution { public: int lengthOfLIS(vectorint nums) { if(nums.size() 1) return nums.size(); vectorint dp(nums.size(), 1); int result 1; for(int i 1; i nums.size(); i){ for(int j 0; j i; j){ if(nums[i] nums[j]){ dp[i] max(dp[i], dp[j] 1); } } result max(result, dp[i]); } return result; } };2.3 时间复杂度优化思路上述解法的时间复杂度是O(n²)对于大规模数据可能不够高效。更优的解法是使用贪心二分查找可以将时间复杂度降到O(nlogn)。基本思路是维护一个可能成为最长递增子序列的候选序列对于每个新元素用二分查找确定它的插入位置。3. 最长连续递增序列问题674题3.1 问题特点分析与300题不同674题要求子序列必须是连续的。这使得问题变得简单因为每个元素只需要与前一个元素比较而不需要与之前所有元素比较。3.2 动态规划解法3.2.1 DP数组定义dp[i]表示以nums[i]结尾的最长连续递增子序列的长度。3.2.2 状态转移方程if nums[i] nums[i-1]: dp[i] dp[i-1] 1 else: dp[i] 13.2.3 代码实现class Solution { public: int findLengthOfLCIS(vectorint nums) { if(nums.empty()) return 0; vectorint dp(nums.size(), 1); int result 1; for(int i 1; i nums.size(); i){ if(nums[i] nums[i-1]){ dp[i] dp[i-1] 1; result max(result, dp[i]); } } return result; } };3.3 空间优化技巧由于dp[i]只依赖于dp[i-1]我们可以用一个变量代替整个dp数组将空间复杂度从O(n)降到O(1)。4. 最长重复子数组问题718题4.1 二维动态规划解法4.1.1 DP数组定义定义dp[i][j]为以A[i-1]和B[j-1]结尾的最长公共子数组的长度。这里使用i-1和j-1是为了方便处理边界条件。4.1.2 状态转移方程if A[i-1] B[j-1]: dp[i][j] dp[i-1][j-1] 1 else: dp[i][j] 04.1.3 代码实现class Solution { public: int findLength(vectorint nums1, vectorint nums2) { int m nums1.size(), n nums2.size(); vectorvectorint dp(m1, vectorint(n1, 0)); int result 0; for(int i 1; i m; i){ for(int j 1; j n; j){ if(nums1[i-1] nums2[j-1]){ dp[i][j] dp[i-1][j-1] 1; result max(result, dp[i][j]); } } } return result; } };4.2 空间优化技巧由于dp[i][j]只依赖于左上方的dp[i-1][j-1]我们可以将二维DP优化为一维通过逆序遍历j来避免覆盖。5. 最长公共子序列问题1143题5.1 与重复子数组的区别最长公共子序列LCS不要求连续这是与718题的主要区别。这使得状态转移方程需要考虑更多情况。5.2 动态规划解法5.2.1 DP数组定义dp[i][j]表示text1前i个字符和text2前j个字符的最长公共子序列长度。5.2.2 状态转移方程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])5.2.3 代码实现class Solution { public: int longestCommonSubsequence(string text1, string text2) { int m text1.size(), n text2.size(); vectorvectorint dp(m1, vectorint(n1, 0)); for(int i 1; i m; i){ for(int j 1; j n; j){ 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[m][n]; } };6. 不相交的线问题1035题6.1 问题转化思路1035题实际上是1143题的变种因为绘制不相交的连线等价于找到两个序列的最长公共子序列。相同的数字可以连接且顺序必须保持一致。6.2 解法实现可以直接使用1143题的解法因为两者本质相同。7. 最大子序和问题53题7.1 动态规划解法7.1.1 DP数组定义dp[i]表示以nums[i]结尾的最大子序和。7.1.2 状态转移方程dp[i] max(nums[i], dp[i-1] nums[i])7.1.3 代码实现class Solution { public: int maxSubArray(vectorint nums) { int n nums.size(); if(n 0) return 0; vectorint dp(n); dp[0] nums[0]; int result dp[0]; for(int i 1; i n; i){ dp[i] max(nums[i], dp[i-1] nums[i]); result max(result, dp[i]); } return result; } };7.2 空间优化同样可以优化为O(1)空间只需维护前一个状态的dp值。8. 动态规划解题方法论总结8.1 解题通用步骤定义DP数组的含义确定初始条件推导状态转移方程确定遍历顺序考虑空间优化8.2 常见错误与调试技巧边界条件处理不当特别注意数组为空或只有一个元素的情况DP数组初始化错误根据问题需求正确初始化遍历顺序错误确保计算当前状态时所需的前置状态已经计算结果提取位置错误有时结果不是dp[n-1]需要在遍历过程中记录最大值8.3 不同问题的对比分析问题类型连续性要求状态转移特点典型例题最长递增子序列非连续需要比较前面所有元素300题最长连续递增序列连续只需比较前一个元素674题最长重复子数组连续二维DP相等时从左上角转移718题最长公共子序列非连续二维DP不等时考虑左或上1143题最大子序和连续一维DP选择是否接上前面的和53题在实际面试和解题过程中理解这些问题的共性和差异能够帮助我们快速识别问题类型并选择合适的解法。动态规划虽然有一定难度但通过大量练习和总结可以掌握其核心思想并灵活应用。
1. 动态规划在子序列问题中的应用概述动态规划Dynamic Programming是解决子序列问题的利器尤其擅长处理那些需要全局最优解的序列匹配问题。在算法领域子序列问题通常分为两大类连续子序列和非连续子序列。连续子序列要求元素在原序列中必须相邻而非连续子序列则允许元素之间存在间隔。动态规划解决这类问题的核心思想在于状态转移——通过定义合适的状态表示找出当前状态与之前状态之间的关系从而避免重复计算。对于子序列问题我们通常会定义dp[i]或dp[i][j]来表示以第i个元素结尾或考虑前i个元素时的某种最优解。2. 最长递增子序列问题解析300题2.1 问题定义与基本思路最长递增子序列Longest Increasing Subsequence, LIS问题要求在一个无序的整数序列中找到一个子序列使得这个子序列的元素严格递增并且这个子序列的长度尽可能长。这里的子序列不要求连续但必须保持原始顺序。例如对于序列[10,9,2,5,3,7,101,18]最长的递增子序列是[2,3,7,101]长度为4。2.2 动态规划解法详解2.2.1 DP数组定义我们定义dp[i]为以nums[i]结尾的最长递增子序列的长度。这个定义很关键它保证了我们只需要关注以当前元素结尾的情况而不用考虑全局。2.2.2 状态转移方程对于每个i我们需要检查所有j i的元素if nums[i] nums[j]: dp[i] max(dp[i], dp[j] 1)这个方程的含义是如果当前数字nums[i]比前面的某个数字nums[j]大那么我们可以把nums[i]接在以nums[j]结尾的子序列后面形成一个新的更长的子序列。2.2.3 初始化与遍历顺序每个dp[i]至少为1只包含自己所以初始化为全1数组。遍历顺序是外层循环i从1到n-1内层循环j从0到i-1。2.2.4 完整代码实现class Solution { public: int lengthOfLIS(vectorint nums) { if(nums.size() 1) return nums.size(); vectorint dp(nums.size(), 1); int result 1; for(int i 1; i nums.size(); i){ for(int j 0; j i; j){ if(nums[i] nums[j]){ dp[i] max(dp[i], dp[j] 1); } } result max(result, dp[i]); } return result; } };2.3 时间复杂度优化思路上述解法的时间复杂度是O(n²)对于大规模数据可能不够高效。更优的解法是使用贪心二分查找可以将时间复杂度降到O(nlogn)。基本思路是维护一个可能成为最长递增子序列的候选序列对于每个新元素用二分查找确定它的插入位置。3. 最长连续递增序列问题674题3.1 问题特点分析与300题不同674题要求子序列必须是连续的。这使得问题变得简单因为每个元素只需要与前一个元素比较而不需要与之前所有元素比较。3.2 动态规划解法3.2.1 DP数组定义dp[i]表示以nums[i]结尾的最长连续递增子序列的长度。3.2.2 状态转移方程if nums[i] nums[i-1]: dp[i] dp[i-1] 1 else: dp[i] 13.2.3 代码实现class Solution { public: int findLengthOfLCIS(vectorint nums) { if(nums.empty()) return 0; vectorint dp(nums.size(), 1); int result 1; for(int i 1; i nums.size(); i){ if(nums[i] nums[i-1]){ dp[i] dp[i-1] 1; result max(result, dp[i]); } } return result; } };3.3 空间优化技巧由于dp[i]只依赖于dp[i-1]我们可以用一个变量代替整个dp数组将空间复杂度从O(n)降到O(1)。4. 最长重复子数组问题718题4.1 二维动态规划解法4.1.1 DP数组定义定义dp[i][j]为以A[i-1]和B[j-1]结尾的最长公共子数组的长度。这里使用i-1和j-1是为了方便处理边界条件。4.1.2 状态转移方程if A[i-1] B[j-1]: dp[i][j] dp[i-1][j-1] 1 else: dp[i][j] 04.1.3 代码实现class Solution { public: int findLength(vectorint nums1, vectorint nums2) { int m nums1.size(), n nums2.size(); vectorvectorint dp(m1, vectorint(n1, 0)); int result 0; for(int i 1; i m; i){ for(int j 1; j n; j){ if(nums1[i-1] nums2[j-1]){ dp[i][j] dp[i-1][j-1] 1; result max(result, dp[i][j]); } } } return result; } };4.2 空间优化技巧由于dp[i][j]只依赖于左上方的dp[i-1][j-1]我们可以将二维DP优化为一维通过逆序遍历j来避免覆盖。5. 最长公共子序列问题1143题5.1 与重复子数组的区别最长公共子序列LCS不要求连续这是与718题的主要区别。这使得状态转移方程需要考虑更多情况。5.2 动态规划解法5.2.1 DP数组定义dp[i][j]表示text1前i个字符和text2前j个字符的最长公共子序列长度。5.2.2 状态转移方程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])5.2.3 代码实现class Solution { public: int longestCommonSubsequence(string text1, string text2) { int m text1.size(), n text2.size(); vectorvectorint dp(m1, vectorint(n1, 0)); for(int i 1; i m; i){ for(int j 1; j n; j){ 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[m][n]; } };6. 不相交的线问题1035题6.1 问题转化思路1035题实际上是1143题的变种因为绘制不相交的连线等价于找到两个序列的最长公共子序列。相同的数字可以连接且顺序必须保持一致。6.2 解法实现可以直接使用1143题的解法因为两者本质相同。7. 最大子序和问题53题7.1 动态规划解法7.1.1 DP数组定义dp[i]表示以nums[i]结尾的最大子序和。7.1.2 状态转移方程dp[i] max(nums[i], dp[i-1] nums[i])7.1.3 代码实现class Solution { public: int maxSubArray(vectorint nums) { int n nums.size(); if(n 0) return 0; vectorint dp(n); dp[0] nums[0]; int result dp[0]; for(int i 1; i n; i){ dp[i] max(nums[i], dp[i-1] nums[i]); result max(result, dp[i]); } return result; } };7.2 空间优化同样可以优化为O(1)空间只需维护前一个状态的dp值。8. 动态规划解题方法论总结8.1 解题通用步骤定义DP数组的含义确定初始条件推导状态转移方程确定遍历顺序考虑空间优化8.2 常见错误与调试技巧边界条件处理不当特别注意数组为空或只有一个元素的情况DP数组初始化错误根据问题需求正确初始化遍历顺序错误确保计算当前状态时所需的前置状态已经计算结果提取位置错误有时结果不是dp[n-1]需要在遍历过程中记录最大值8.3 不同问题的对比分析问题类型连续性要求状态转移特点典型例题最长递增子序列非连续需要比较前面所有元素300题最长连续递增序列连续只需比较前一个元素674题最长重复子数组连续二维DP相等时从左上角转移718题最长公共子序列非连续二维DP不等时考虑左或上1143题最大子序和连续一维DP选择是否接上前面的和53题在实际面试和解题过程中理解这些问题的共性和差异能够帮助我们快速识别问题类型并选择合适的解法。动态规划虽然有一定难度但通过大量练习和总结可以掌握其核心思想并灵活应用。
与shutdown()的本质区别与应用)
