企业官网建设流程全解析

LeetCode 53 最大子数组和：从暴力枚举到动态规划，我是怎么找到状态转移的

最近做到 LeetCode 53「最大子数组和」：

给你一个整数数组nums，请找出一个具有最大和的连续子数组，返回其最大和。

这道题最后的动态规划代码很简单，但我看完题解后发现，真正值得复盘的并不是记住状态转移公式，而是一个自己之前一直没有意识到的问题：

状态之间的依赖方向，不一定和dp数组的遍历方向(由i推导i+1)一致。应该先寻找状态之间天然的依赖关系，再由依赖关系决定计算顺序。

下面记录一下我是怎么从暴力解法走到动态规划，以及中间为什么会卡住。

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[i+1])

也可以写成：

dp[i] = nums[i] + max(0, dp[i+1])

如果dp[i+1] > 0，就把后面的部分接上；

如果dp[i+1] <= 0，后面的部分只会让结果变小，不如从nums[i]处结束。

整个状态依赖关系实际上是：

dp[0] ← dp[1] ← dp[2] ← ... ← dp[n-1]

既然dp[i]依赖dp[i+1]，那么计算顺序自然应该是：

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结尾”之所以通常更容易想到，是因为它的状态依赖方向刚好与我们习惯的数组遍历方向一致。

5. 总结：先找依赖关系，再决定计算顺序

求解DP问题的思考顺序：

1. dp[i]到底表示什么？

2. 按照这个定义，dp[i]天然依赖哪个更小的子问题？

3. 根据这种依赖关系，我应该按照什么顺序计算？（根据dp[i-1]计算dp[i]，还是根据dp[i+1]计算dp[i]）