> For the complete documentation index, see [llms.txt](https://mm.ricky.moe/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mm.ricky.moe/algorithm/algorithm-and-data-structure/dong-tai-gui-hua.md).

# 动态规划

动态规划，英文是Dynamic Programming，简称DP，擅长解决“多阶段决策问题”，利用各个阶段阶段的递推关系，逐个确定每个阶段的最优决策，并最终得到原问题的最优决策。

**动态规划与递归**

* 动态规划本质上不是递归，甚至可以理解是和递归相反的一种算法设计思想。
* 递归是自顶向下的，从顶部开始分解问题，然后通过解决分解出的小问题，从而解决出整个问题
* 动态规划是自底向上的，从底部开始解决问题，按照顺序一步一步扩大问题的规模从而去解决整个问题