动态规划如何降低子集和问题的时间复杂度？

问题1：DP遍历的时候会不会漏掉看起来唯一的2^n条递归分支？ #

你观察到的递归树2^n条分支看起来都是唯一的，其实只是「选法组合」唯一，很多分支的中间计算状态是完全等价的：比如给定元素[1,3,4]，要凑总和10，你选前两个元素得到当前和4，和直接选第三个元素得到当前和4，接下来的可选元素、剩余要凑的差值完全一样，这两条分支后续的所有计算结果100%重合，完全没必要重复跑。
DP的核心逻辑就是记录所有等价的中间状态，常规的子集和DP状态定义为dp[i][j]：表示在前i个元素中，能不能凑出和为j的子集。只要任意一条选法分支能走到「前i个元素凑出j」的状态，这个状态就会被标记为可达，相当于自动覆盖了所有能走到这个状态的选法分支，不会漏任何一种可能的解。 #

问题2：DP为什么能在不丢解的前提下把复杂度降下来？ #

首先要先明确一个概念：子集和的DP复杂度是伪多项式时间，不是严格意义的多项式时间，它的时间复杂度为O(n * target)，n是元素数量，target是要凑的目标和。只有当target的规模是多项式级别的时候，整体复杂度才是多项式级的，如果target大到2^n级别，那复杂度还是指数级的。
它能降复杂度的核心就是合并等价状态：暴力递归是把每个不同的选法组合当成独立分支计算，最多要跑2^n次；但DP不管你有多少种选法能得到同一个和j，都只记录一次这个状态，相当于把成千上万条等价的分支合并成了一次计算，只要总的状态数量（n*target）可控，复杂度自然就降下来了。 #

问题3：如果真的存在2^n种解，DP还能保持低复杂度吗？ #

这个要分你的需求来看：

• 如果你只是要判断「是否存在解」或者「统计解的总数量」：哪怕有2^n种不同的选法都能凑出target，DP依然只需要维护dp[i][j]的可达状态或者计数，不需要枚举每一种具体的选法，复杂度还是保持O(n*target)。
• 如果你需要输出所有具体的子集解：那不管用不用DP，复杂度都必然是指数级的，毕竟你要输出2^n个结果本身就需要对应量级的时间，这种场景下DP最多只能帮你提前剪掉不可能得到解的分支，没法把整体复杂度降到多项式级别。

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