1. 最优子结构（Optimal Substructure）
定义：问题的最优解包含其子问题的最优解。即通过子问题的最优解可以组合得到原问题的最优解。
关键点：
-
子问题的解必须独立且可组合。
-
若子问题的最优解无法推导出全局最优解，则问题不具备最优子结构。
示例：
-
最短路径问题：从A到C的最短路径若经过B，则A到B的路径也必须是A到B的最短路径。
-
编辑距离：将字符串A转换为B的最小操作次数，可通过其前缀子串的编辑距离推导。
反例：
-
最长路径问题：从A到C的最长路径经过B时，A到B的路径未必是最长的，可能需绕远路。
2. 重叠子问题（Overlapping Subproblems）
定义：问题分解后的子问题会被重复计算多次。
关键点：
-
递归求解时，子问题的重复计算导致效率低下。
-
动态规划通过存储子问题的解（记忆化或表格填充）避免重复计算。
示例：
-
斐波那契数列：计算
fib(n)需重复计算fib(n-1)和fib(n-2)。 -
矩阵链乘法：不同分割点的子链乘法次数会被多次计算。
反例：
-
快速排序：子数组的排序独立且无重叠，适合分治而非DP。
3. 无后效性（No Aftereffect）
定义：当前状态确定后，后续决策仅依赖当前状态，与之前状态的历史路径无关。
关键点：
-
状态转移方程仅依赖于当前状态，而非状态如何到达的过程。
示例：
-
背包问题：在容量为
w时选择第i个物品的最优解，仅依赖前i-1个物品在容量w或w - weight[i]时的状态。 -
股票买卖问题：某天的最大收益仅依赖前一天的持有或未持有状态。
反例：
-
某些复杂路径问题：若路径选择需记录完整历史路径（如避开某些节点），则难以用DP高效解决。
4. 状态转移方程的可行性
定义：能够明确定义状态，并建立状态之间的递推关系（即状态转移方程）。
关键点：
-
状态需能完整描述问题的当前进展。
-
状态转移需能通过数学或逻辑表达式清晰表达。
示例：
-
最长公共子序列（LCS）：状态
dp[i][j]表示字符串A前i个字符与B前j个字符的LCS长度，转移方程为：
-
爬楼梯问题：状态
dp[n]表示到达第n阶的方法数，转移方程为dp[n] = dp[n-1] + dp[n-2]。
判断步骤总结
-
分解子问题：尝试将问题拆解为更小的子问题。
-
验证最优子结构：确认子问题的最优解能组合成全局最优解。
-
检查重叠性：观察子问题是否被重复计算（递归树是否有重复节点）。
-
确保无后效性：定义状态时，确保后续决策仅依赖当前状态。
-
建立状态转移方程：若上述条件满足，尝试形式化状态转移关系。
动态规划 vs. 其他算法
| 条件 | 动态规划 | 贪心算法 | 分治算法 |
|---|---|---|---|
| 最优子结构 | 必须满足 | 必须满足 | 必须满足 |
| 重叠子问题 | 必须满足 | 不要求 | 不要求 |
| 无后效性 | 必须满足 | 不要求 | 不要求 |
| 贪心选择性质 | 不要求 | 必须满足 | 不要求 |
| 子问题独立性 | 不要求 | 不要求 | 必须满足 |
典型适用场景
-
最优化问题：如最短路径、最大利润、最小代价等。
-
计数问题：如路径总数、组合方式数等。
-
序列决策问题：如字符串编辑、股票买卖、游戏策略等。
-
资源分配问题：如背包问题、任务调度等。
反例：不适合动态规划的问题
-
最长路径问题：不具备最优子结构。
-
NP完全问题（如旅行商问题的暴力解法）：状态空间爆炸，无法高效处理。
-
强依赖历史路径的问题：如需记录完整操作序列的场景。
