笔记

复仇者_零

2025-02-15 20:30:13

发布于：浙江

23阅读

0回复

0点赞

动态规划

动态规划（Dynamic Programming，DP）是一种通过把原问题分解成子问题，再从子问题的解得到原问题的解的方法。
动态规划的解题步骤:
- 定义子问题(确定状态)：将原问题分解成若干个子问题，子问题之间具有重叠性。
- 划分子问题之间的关系（划分阶段） ：定义状态之间的关系，即子问题之间的依赖关系。
- 确定状态转移方程（确定方程） ：对于每个子问题，定义原问题的状态转移方程。
- 寻找子问题的最优解（求解阶段） ：利用子问题的最优解，递归似地求解原问题的最优解。
动态规划的适用性：
- 最优子结构：动态规划适用于具有最优子结构的问题，即问题的最优解包含子问题的最优解。
- 子问题重叠性：动态规划通过重叠子问题的解来避免重复计算，从而减少计算量。