尧图网页设计 
LeetCode 53 最大子数组和从暴力枚举到动态规划我是怎么找到状态转移的最近做到 LeetCode 53「最大子数组和」给你一个整数数组nums请找出一个具有最大和的连续子数组返回其最大和。这道题最后的动态规划代码很简单但我看完题解后发现真正值得复盘的并不是记住状态转移公式而是一个自己之前一直没有意识到的问题状态之间的依赖方向不一定和dp数组的遍历方向(由i推导i1)一致。应该先寻找状态之间天然的依赖关系再由依赖关系决定计算顺序。下面记录一下我是怎么从暴力解法走到动态规划以及中间为什么会卡住。1. 从暴力解法开始寻找子问题最开始想到的是暴力枚举所有连续子数组。两层循环外层循环确定子数组的开头内层循环不断向后扩展确定子数组的结尾。def maxSubArray(nums): ans float(-inf) for i in range(len(nums)): cur_sum 0 for j in range(i, len(nums)): cur_sum nums[j] ans max(ans, cur_sum) return ans时间复杂度为O(n²)。写到这里我注意到外层循环每执行一次其实都解决了一个很明确的子问题i 0求以 nums[0] 开头的最大连续子数组和 i 1求以 nums[1] 开头的最大连续子数组和 i 2求以 nums[2] 开头的最大连续子数组和 ...既然这些子问题长得如此相似很自然地可以定义dp[i] 以 nums[i] 开头的最大连续子数组和到这里其实已经有了 DP 的状态。但我接下来走进了一个误区。2. 第一次错误尝试有了 dp[0]就想着怎么推出 dp[1]因为暴力解法本身是从左向右执行的所以我潜意识里的思考顺序也是已经求出了 dp[0] ↓ 接下来要求 dp[1] ↓ 研究 dp[0] 和 dp[1] 的关系 ↓ 尝试 dp[0] → dp[1]甚至一开始我还错误地认为dp[1] dp[0] - nums[0]例如nums [-2, 1, -3, 4, -1, 2, 1, -5, 4]dp[0]比较的是[-2] [-2, 1] [-2, 1, -3] [-2, 1, -3, 4] ...而dp[1]比较的是[1] [1, -3] [1, -3, 4] ...乍一看似乎把dp[0]对应的子数组去掉第一个元素就可以得到dp[1]。但情况可能是dp[0] nums[0]此时从dp[0]就无法得出dp[1]了。我当时就是在这里卡住了。现在回头看真正的问题其实不是这个状态定义得不好而是我的思考方式存在一个默认前提因为 dp[0] 已经算出来了所以 dp[1] 就应该由 dp[0] 推出来。但 DP 并没有这个要求。3. 真正的突破不是 dp[0] → dp[1]也可以是 dp[2] → dp[1]重新回到状态定义dp[i] 以 nums[i] 开头的最大连续子数组和与其问已经有了dp[i-1]怎么得到dp[i]不如直接问按照 dp[i] 的定义它天然和哪个子问题有关假设现在要求dp[1]。一个以nums[1]开头的连续子数组只有两种可能① 只选择 nums[1] ② 选择 nums[1]然后继续向后延伸如果继续向后因为要求连续下一个位置一定是nums[2]。那么后面需要解决的问题是什么恰好就是以 nums[2] 开头的最大连续子数组和也就是dp[2]所以真正天然的状态依赖其实是dp[1] ← dp[2]而不是我一开始一直尝试的dp[0] → dp[1]一般化以后dp[i] max(nums[i], nums[i] dp[i1])也可以写成dp[i] nums[i] max(0, dp[i1])如果dp[i1] 0就把后面的部分接上如果dp[i1] 0后面的部分只会让结果变小不如从nums[i]处结束。整个状态依赖关系实际上是dp[0] ← dp[1] ← dp[2] ← ... ← dp[n-1]既然dp[i]依赖dp[i1]那么计算顺序自然应该是dp[n-1] → dp[n-2] → ... → dp[1] → dp[0]于是代码也就出来了class Solution: def maxSubArray(self, nums: list[int]) - int: n len(nums) dp [0] * n dp[n - 1] nums[n - 1] for i in range(n - 2, -1, -1): dp[i] nums[i] max(0, dp[i 1]) return max(dp)这也是我做这道题时最大的收获不要因为 dp[i-1] 已经被算出来了就强行思考如何用 dp[i-1] 推导 dp[i]。应该先根据 dp[i] 的定义寻找它天然依赖的子问题再由依赖关系决定 DP 的计算顺序。换句话说错误的思考顺序 先决定从左往右计算 ↓ dp[i-1] 已经有了 ↓ 想办法用 dp[i-1] 推 dp[i] 更合理的思考顺序 先定义 dp[i] ↓ 分析 dp[i] 天然依赖哪个子问题 ↓ 得到状态转移 ↓ 最后根据依赖关系决定计算顺序不是“已经算出了什么”决定状态转移而应该是“状态转移需要什么”决定先算什么。4. 为什么常见题解更喜欢定义“以 i 结尾”理解了上面的思路之后再看常见题解就很好理解了。大多数题解会定义dp[i] 以 nums[i] 结尾的最大连续子数组和现在考虑一个必须以nums[i]结尾的连续子数组同样只有两种情况① 从 nums[i] 重新开始 ② 接在前面的连续子数组后面如果选择第二种情况那么前面的部分自然应该选择以 nums[i-1] 结尾的最大连续子数组也就是dp[i-1]。所以dp[i] max(nums[i], nums[i] dp[i-1])即dp[i] nums[i] max(0, dp[i-1])此时状态依赖变成dp[0] → dp[1] → dp[2] → ... → dp[n-1]因此可以很自然地从左向右计算class Solution: def maxSubArray(self, nums: list[int]) - int: n len(nums) dp [0] * n dp[0] nums[0] for i in range(1, n): dp[i] nums[i] max(0, dp[i - 1]) return max(dp)所以“以i开头”和“以i结尾”其实是完全对称的两种定义状态定义状态转移计算方向以i开头的最大子数组和dp[i] nums[i] max(0, dp[i1])从右向左以i结尾的最大子数组和dp[i] nums[i] max(0, dp[i-1])从左向右我的“以i开头”并没有定义错。真正的问题是定义了一个天然依赖右侧状态的 DP却还在按照从左向右的顺序思考。而“以i结尾”之所以通常更容易想到是因为它的状态依赖方向刚好与我们习惯的数组遍历方向一致。5. 总结先找依赖关系再决定计算顺序求解DP问题的思考顺序dp[i]到底表示什么按照这个定义dp[i]天然依赖哪个更小的子问题根据这种依赖关系我应该按照什么顺序计算根据dp[i-1]计算dp[i]还是根据dp[i1]计算dp[i] 最大子数组和 #python解法 #动态规划
LeetCode 53 最大子数组和从暴力枚举到动态规划我是怎么找到状态转移的最近做到 LeetCode 53「最大子数组和」给你一个整数数组nums请找出一个具有最大和的连续子数组返回其最大和。这道题最后的动态规划代码很简单但我看完题解后发现真正值得复盘的并不是记住状态转移公式而是一个自己之前一直没有意识到的问题状态之间的依赖方向不一定和dp数组的遍历方向(由i推导i1)一致。应该先寻找状态之间天然的依赖关系再由依赖关系决定计算顺序。下面记录一下我是怎么从暴力解法走到动态规划以及中间为什么会卡住。1. 从暴力解法开始寻找子问题最开始想到的是暴力枚举所有连续子数组。两层循环外层循环确定子数组的开头内层循环不断向后扩展确定子数组的结尾。def maxSubArray(nums): ans float(-inf) for i in range(len(nums)): cur_sum 0 for j in range(i, len(nums)): cur_sum nums[j] ans max(ans, cur_sum) return ans时间复杂度为O(n²)。写到这里我注意到外层循环每执行一次其实都解决了一个很明确的子问题i 0求以 nums[0] 开头的最大连续子数组和 i 1求以 nums[1] 开头的最大连续子数组和 i 2求以 nums[2] 开头的最大连续子数组和 ...既然这些子问题长得如此相似很自然地可以定义dp[i] 以 nums[i] 开头的最大连续子数组和到这里其实已经有了 DP 的状态。但我接下来走进了一个误区。2. 第一次错误尝试有了 dp[0]就想着怎么推出 dp[1]因为暴力解法本身是从左向右执行的所以我潜意识里的思考顺序也是已经求出了 dp[0] ↓ 接下来要求 dp[1] ↓ 研究 dp[0] 和 dp[1] 的关系 ↓ 尝试 dp[0] → dp[1]甚至一开始我还错误地认为dp[1] dp[0] - nums[0]例如nums [-2, 1, -3, 4, -1, 2, 1, -5, 4]dp[0]比较的是[-2] [-2, 1] [-2, 1, -3] [-2, 1, -3, 4] ...而dp[1]比较的是[1] [1, -3] [1, -3, 4] ...乍一看似乎把dp[0]对应的子数组去掉第一个元素就可以得到dp[1]。但情况可能是dp[0] nums[0]此时从dp[0]就无法得出dp[1]了。我当时就是在这里卡住了。现在回头看真正的问题其实不是这个状态定义得不好而是我的思考方式存在一个默认前提因为 dp[0] 已经算出来了所以 dp[1] 就应该由 dp[0] 推出来。但 DP 并没有这个要求。3. 真正的突破不是 dp[0] → dp[1]也可以是 dp[2] → dp[1]重新回到状态定义dp[i] 以 nums[i] 开头的最大连续子数组和与其问已经有了dp[i-1]怎么得到dp[i]不如直接问按照 dp[i] 的定义它天然和哪个子问题有关假设现在要求dp[1]。一个以nums[1]开头的连续子数组只有两种可能① 只选择 nums[1] ② 选择 nums[1]然后继续向后延伸如果继续向后因为要求连续下一个位置一定是nums[2]。那么后面需要解决的问题是什么恰好就是以 nums[2] 开头的最大连续子数组和也就是dp[2]所以真正天然的状态依赖其实是dp[1] ← dp[2]而不是我一开始一直尝试的dp[0] → dp[1]一般化以后dp[i] max(nums[i], nums[i] dp[i1])也可以写成dp[i] nums[i] max(0, dp[i1])如果dp[i1] 0就把后面的部分接上如果dp[i1] 0后面的部分只会让结果变小不如从nums[i]处结束。整个状态依赖关系实际上是dp[0] ← dp[1] ← dp[2] ← ... ← dp[n-1]既然dp[i]依赖dp[i1]那么计算顺序自然应该是dp[n-1] → dp[n-2] → ... → dp[1] → dp[0]于是代码也就出来了class Solution: def maxSubArray(self, nums: list[int]) - int: n len(nums) dp [0] * n dp[n - 1] nums[n - 1] for i in range(n - 2, -1, -1): dp[i] nums[i] max(0, dp[i 1]) return max(dp)这也是我做这道题时最大的收获不要因为 dp[i-1] 已经被算出来了就强行思考如何用 dp[i-1] 推导 dp[i]。应该先根据 dp[i] 的定义寻找它天然依赖的子问题再由依赖关系决定 DP 的计算顺序。换句话说错误的思考顺序 先决定从左往右计算 ↓ dp[i-1] 已经有了 ↓ 想办法用 dp[i-1] 推 dp[i] 更合理的思考顺序 先定义 dp[i] ↓ 分析 dp[i] 天然依赖哪个子问题 ↓ 得到状态转移 ↓ 最后根据依赖关系决定计算顺序不是“已经算出了什么”决定状态转移而应该是“状态转移需要什么”决定先算什么。4. 为什么常见题解更喜欢定义“以 i 结尾”理解了上面的思路之后再看常见题解就很好理解了。大多数题解会定义dp[i] 以 nums[i] 结尾的最大连续子数组和现在考虑一个必须以nums[i]结尾的连续子数组同样只有两种情况① 从 nums[i] 重新开始 ② 接在前面的连续子数组后面如果选择第二种情况那么前面的部分自然应该选择以 nums[i-1] 结尾的最大连续子数组也就是dp[i-1]。所以dp[i] max(nums[i], nums[i] dp[i-1])即dp[i] nums[i] max(0, dp[i-1])此时状态依赖变成dp[0] → dp[1] → dp[2] → ... → dp[n-1]因此可以很自然地从左向右计算class Solution: def maxSubArray(self, nums: list[int]) - int: n len(nums) dp [0] * n dp[0] nums[0] for i in range(1, n): dp[i] nums[i] max(0, dp[i - 1]) return max(dp)所以“以i开头”和“以i结尾”其实是完全对称的两种定义状态定义状态转移计算方向以i开头的最大子数组和dp[i] nums[i] max(0, dp[i1])从右向左以i结尾的最大子数组和dp[i] nums[i] max(0, dp[i-1])从左向右我的“以i开头”并没有定义错。真正的问题是定义了一个天然依赖右侧状态的 DP却还在按照从左向右的顺序思考。而“以i结尾”之所以通常更容易想到是因为它的状态依赖方向刚好与我们习惯的数组遍历方向一致。5. 总结先找依赖关系再决定计算顺序求解DP问题的思考顺序dp[i]到底表示什么按照这个定义dp[i]天然依赖哪个更小的子问题根据这种依赖关系我应该按照什么顺序计算根据dp[i-1]计算dp[i]还是根据dp[i1]计算dp[i]