动态规划时间复杂度疑问：分割等和子集Top-Down DP为何是O(n*sum)？

先明确核心逻辑：你对纯递归无记忆化版本的时间复杂度判断是对的，但记忆化直接砍掉了大量重复计算，把复杂度从指数级降到了多项式级。

1. 纯递归无记忆化：确实是O(2^n) #

每个元素都有「选」和「不选」两种决策，递归树会展开成2^n个节点——比如n=10就有1024个节点，n=20直接破百万，这就是指数级复杂度的来源。但这里有个关键问题：大量递归路径会重复计算同一个状态。

举个例子：假设数组是[2,3,5,7]，目标和是7。处理到第3个元素（5）时，剩余目标和是4的状态，可能在「选了2、没选3」和「没选2、选了3」这两条不同路径中都出现，纯递归会对这个状态重新计算两次，但其实结果是完全一致的。

2. 记忆化DP：把重复状态只算一次 #

Top-Down DP的核心是记录已经计算过的状态，避免重复递归。我们的状态由两个变量唯一确定：

• i：当前处理到第i个元素（从0到n-1，共n种可能）
• remaining：当前还需要凑的目标和（从0到sum/2，共sum/2+1种可能）

总共有 n * (sum/2 + 1) 种不同的状态，也就是O(n*sum)个状态。每个状态只会被计算一次：

• 第一次遇到状态(i, remaining)时，我们递归计算「选当前元素」和「不选当前元素」的结果，然后把结果存在记忆化表（比如二维数组dp[i][remaining]）里。
• 之后再遇到相同的(i, remaining)时，直接从记忆化表中取结果，不需要再递归展开分支。

每个状态的处理时间是O(1)（只需要判断选或不选的结果，合并返回），所以总时间复杂度就是状态数的量级：O(n*sum)。

3. 对应到你看的实现代码 #

你看到的递归分支（选/不选）只是状态计算时的两个子问题，但这两个子问题对应的状态如果已经被计算过，就不会再递归下去。比如代码里的记忆化数组会标记dp[i][j]是否已经计算过，计算过的直接返回，不会重复遍历整个递归树。

简单说：纯递归是遍历所有可能的子集（2^n个），而记忆化DP是遍历所有可能的「处理位置+剩余目标和」组合（n*sum个），后者的数量远小于前者（只要sum不是指数级大）。

内容的提问来源于stack exchange，提问作者charactersum