所有递归问题都能用动态规划解决吗？为何不放弃分治只用DP？

问题1：是否所有递归问题都有对应的DP解法？ #

答案是否定的。
动态规划的核心价值是通过缓存重复计算的子问题结果降低时间复杂度，因此它的适用前提是问题满足两个核心特征：重叠子问题、最优子结构（求最优解场景需要），不是所有递归问题都符合这个要求。
举几个很常见的反例：

• 递归实现n的阶乘：子问题是f(n) = n * f(n-1)，每个子问题只会被计算一次，完全没有重叠，用DP反而需要额外空间存储子问题结果，纯属多此一举，也不存在对应的DP优化空间。
• 递归实现快速排序：拆分出的子问题是处理不同的数组区间，所有子问题完全独立无重叠，没有重复计算的部分，自然也用不上DP。
• 递归遍历二叉树的所有根到叶子路径：每个子问题处理的是独立的子树路径，没有重叠计算场景，DP没有用武之地。

问题2：如果忽略适用边界，为什么不放弃分治算法，只使用DP解题？ #

哪怕不考虑DP的适用限制，分治算法也有不可替代的价值：

• 空间成本更低：DP不管是自顶向下的记忆化搜索还是自底向上的迭代实现，都需要额外的空间存储子问题的解，而很多分治算法可以做到原地操作，仅需要递归栈的额外空间。比如快速排序最优场景空间复杂度仅为O(logn)，如果硬套DP实现，反而要额外存储大量不会重复使用的子问题结果，空间成本会高很多。
• 实现更简单易维护：对于没有重叠子问题的场景，分治的实现逻辑直接贴合问题的拆分思路，没有额外的状态定义、状态转移、缓存维护的成本。比如归并排序，直接按区间拆分再合并即可，硬套DP反而要写很多冗余代码，可读性和可维护性都会变差。
• 部分场景时间效率更高：对于没有重叠子问题的问题，分治不需要做额外的缓存读写操作，运行效率反而更高。比如快速傅里叶变换（FFT）、凸包问题的分治解法，本身就没有可复用的子问题结果，用DP不仅带不来时间优化，反而会因为缓存操作拖慢运行速度。

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