LeetCode 热题 100 精讲 | 动态规划进阶篇：最大子数组和 · 分割等和子集 · 最长公共子序列 · 打家劫舍 III

一、53. 最大子数组和 题目链接LeetCode 53. 最大子数组和 题目描述给你一个整数数组nums请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。示例输入nums [-2,1,-3,4,-1,2,1,-5,4] 输出6 解释连续子数组 [4,-1,2,1] 的和最大为 6。 输入nums [1] 输出1 思路分析最大子数组和是动态规划的经典入门题。定义dp[i]表示以nums[i]结尾的连续子数组的最大和。对于每个位置i要么把nums[i]接在dp[i-1]后面继续累加要么以nums[i]自己作为新子数组的开头取两者中较大的那个即dp[i] max(nums[i], dp[i-1] nums[i])。最终答案就是dp数组中的最大值。这里也可以用一个变量滚动记录把空间复杂度降到 O(1)。 代码实现Cclass Solution { public: int maxSubArray(vectorint nums) { int cur nums[0]; int maxSum nums[0]; for (int i 1; i nums.size(); i) { cur max(nums[i], cur nums[i]); maxSum max(maxSum, cur); } return maxSum; } }; 相关学习资源文章07— 最大子数组和【LeetCode 53】腾讯云开发者社区—— 动态规划思路清晰还讲了空间优化文章力扣53最大子数组和【C】CSDN—— 解释了为什么滑动窗口不适用DP 状态推导详细免责声明以上链接均来自公开网络。若存在侵权问题请联系删除。⏱ 复杂度分析时间复杂度O(n)一次遍历。空间复杂度O(1)只用常数个变量。二、416. 分割等和子集 题目链接LeetCode 416. 分割等和子集 题目描述给你一个只包含正整数的非空数组nums判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。示例输入nums [1,5,11,5] 输出true 解释数组可以分割成 [1, 5, 5] 和 [11]。 输入nums [1,2,3,5] 输出false 解释数组不能分割成两个元素和相等的子集。 思路分析这道题的关键在于将其转化为 0-1 背包问题。先计算数组的总和如果总和是奇数直接返回 false如果总和是偶数那么目标就是判断能否从数组中选出一些元素使它们的和等于总和的一半。这就相当于一个背包容量为sum/2的 0-1 背包问题每个元素只能选一次问能否恰好装满背包。定义dp[j]表示能否凑出总和j状态转移方程为dp[j] dp[j] || dp[j - nums[i]]。外层循环遍历每个元素内层循环从sum/2倒序遍历到nums[i]这样可以保证每个元素只被使用一次。 代码实现Cclass Solution { public: bool canPartition(vectorint nums) { int sum 0; for (int num : nums) sum num; if (sum % 2 ! 0) return false; int target sum / 2; vectorbool dp(target 1, false); dp[0] true; for (int num : nums) { for (int j target; j num; j--) { dp[j] dp[j] || dp[j - num]; } } return dp[target]; } }; 相关学习资源文章动态规划分割等和子集可以用01背包腾讯云开发者社区—— 代码随想录出品把背包建模讲得很透彻文章【动态规划/背包问题】如何将原问题抽象为「01 背包」问题腾讯云开发者社区—— 深入讲解“建模”能力帮助举一反三免责声明以上链接均来自公开网络。若存在侵权问题请联系删除。⏱ 复杂度分析时间复杂度O(n × target)其中 target sum/2。空间复杂度O(target)dp 数组的大小。三、1143. 最长公共子序列 题目链接LeetCode 1143. 最长公共子序列 题目描述给定两个字符串text1和text2返回这两个字符串的最长公共子序列的长度。子序列是指在不改变字符相对顺序的情况下删除某些字符后形成的新字符串。示例输入text1 abcde, text2 ace 输出3 解释最长公共子序列是 ace长度为 3。 输入text1 abc, text2 def 输出0 思路分析定义dp[i][j]表示text1的前i个字符和text2的前j个字符的最长公共子序列长度。当text1[i-1] text2[j-1]时dp[i][j] dp[i-1][j-1] 1当不相等时dp[i][j] max(dp[i-1][j], dp[i][j-1])。初始状态dp[0][j] 0和dp[i][0] 0最后返回dp[m][n]。这个二维 DP 表格的填充过程就是不断比较两个字符串的字符逐步构建出最优解。 代码实现Cclass Solution { public: int longestCommonSubsequence(string text1, string text2) { int m text1.size(), n text2.size(); vectorvectorint dp(m 1, vectorint(n 1, 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]; } }; 相关学习资源文章【Leetcode刷题Python】1143. 最长公共子序列阿里云开发者社区—— 思路清晰附 Python 实现文章LeetCode 1143初中级算法题解 - 动态规划腾讯云开发者社区—— 图文结合对 DP 表格的填充过程解释得很详细免责声明以上链接均来自公开网络。若存在侵权问题请联系删除。⏱ 复杂度分析时间复杂度O(m × n)m 和 n 分别是两个字符串的长度。空间复杂度O(m × n)二维 dp 数组的大小。四、337. 打家劫舍 III 题目链接LeetCode 337. 打家劫舍 III 题目描述在上次打劫完一条街道之后和一圈房屋后小偷又发现了一个新的可行窃的地区。这个地区只有一个入口我们称之为“根”。除了“根”之外每栋房子有且只有一个“父”房子与之相连。如果两个直接相连的房子在同一天晚上被打劫房屋将自动报警。计算在不触动警报的情况下小偷一晚能够盗取的最高金额。示例输入root [3,2,3,null,3,null,1] 输出7 解释小偷一晚能盗取的最高金额 3 3 1 7。 思路分析这道题是树形 DP 的经典题。对于每个节点我们考虑两种状态偷当前节点或不偷当前节点。用后序遍历的方式先处理左子树和右子树再处理当前节点。定义递归函数返回一个长度为 2 的数组dpdp[0]表示不偷当前节点时该子树能获得的最大金额dp[1]表示偷当前节点时该子树能获得的最大金额。状态转移不偷当前节点时左右子节点可以偷也可以不偷取最大值相加偷当前节点时左右子节点都不能偷取左右子节点不偷的值加上当前节点的值。最终结果就是根节点两种状态的最大值。 代码实现Cclass Solution { public: int rob(TreeNode* root) { vectorint res dfs(root); return max(res[0], res[1]); } vectorint dfs(TreeNode* node) { if (!node) return {0, 0}; vectorint left dfs(node-left); vectorint right dfs(node-right); int notRob max(left[0], left[1]) max(right[0], right[1]); int rob node-val left[0] right[0]; return {notRob, rob}; } }; 相关学习资源文章leetcode 第337题 打家劫舍 III 树形dpCSDN—— 代码简洁思路讲解清楚免责声明以上链接均来自公开网络。若存在侵权问题请联系删除。⏱ 复杂度分析时间复杂度O(n)每个节点被访问一次。空间复杂度O(h)h 为树高递归调用栈的深度。结语动态规划进阶篇的四道题代表了 DP 的不同应用场景一维线性 DP最大子数组和、0-1 背包问题分割等和子集、二维字符串 DP最长公共子序列、树形 DP打家劫舍 III。从一维数组到二维表格从线性结构到树形结构这四道题基本涵盖了面试中动态规划的高频考察方向。吃透这些题动态规划的能力会上一个台阶。建议刷题顺序先做最大子数组和理解 DP 的基本状态定义再做最长公共子序列熟悉二维 DP 表格的填充然后用分割等和子集理解背包问题的建模能力最后用打家劫舍 III 挑战树形 DP。下一篇将进入动态规划高阶篇编辑距离、最长回文子序列、股票系列敬请期待。如果本文对你有帮助欢迎点赞、收藏、转发你的支持是我持续创作的动力 ❤️免责声明本文部分解题思路参考了力扣官方题解及社区优秀文章相关链接均来自公开网络。若存在侵权问题请联系删除。