动态规划（Dynamic Programming, DP）#

空间换时间。

什么时候不适合使用动态规划#

动态规划（Dynamic Programming, DP）在解决某些问题时非常高效，但并不是所有问题都适合用动态规划。以下几种情况中，动态规划通Answer：

1. 问题没有最优子结构性质（Optimal substructur）
   • 动态规划的前提是问题具有最优子结构，即子问题的最优解能构成原问题的最优解。
   • 如果子问题的最优解不能组合成原问题的最优解，则动态规划无效。例如，寻找路径中有“全局约束”或路径顺序要求的问题可能不具备最优子结构。
2. 问题没有重叠子问题（Overlapping sub-problems）
   • 动态规划的另一前提是存在重叠子问题，即同一个子问题会被多次计算。
   • 如果问题的每个子问题都是独立且只被计算一次，动态规划的优势就消失了。在这种情况下，通常使用分治法更合适。
3. 状态和状态转移方程难以定义
   • 如果问题很难划分为明确的状态和状态转移方程，设计动态规划的解法会变得非常复杂。
   • 有些问题的状态空间过于庞大或转移条件不规则，导致无法找到合适的转移方程，这时也不适合用动态规划。
4. 需要获得所有解，而不仅仅是最优解
   • 动态规划主要用于寻找问题的最优解或计数解的数目，而不是用于获取所有可能的解。
   • 对于要求枚举所有解的组合问题，通常回溯法或递归更合适。
5. 问题是非确定性或不满足最优解递推条件
   • 动态规划依赖于确定性的递推过程，而在概率性、非确定性问题中，不同路径的概率差异或条件差异可能导致DP的逻辑失效。
   • 此类问题往往用其他方法（如随机算法、启发式算法）更为适合。