> For the complete documentation index, see [llms.txt](https://shuixn.gitbook.io/notebook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://shuixn.gitbook.io/notebook/shu-ju-jie-gou-he-suan-fa/dong-tai-gui-hua.md).

# 动态规划

## 定义

Dynamic programming，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

## 性质

1. 重叠子问题：它将问题重新组合成子问题，为了避免多次解决这些子问题，它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。因此，动态规划保存递归时的结果，因而不会在解决同样的问题时花费时间。
2. 最优子结构：局部最优解能决定全局最优解（对有些问题这个要求并不能完全满足，故有时需要引入一定的近似）。

## 适用情况

1. 最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。
2. 无后效性。即子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。
3. 子问题重叠性质。指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率，降低了时间复杂度。

## 实现

解题流程：

1. 暴力的递归
2. 带备忘的自顶向下法（记忆化搜索）；
3. 自底向上法（将子问题按规模排序，类似于递推）。

## 算法

1. 最长公共子序列
2. Floyd-Warshall算法
3. Viterbi算法

## 参考

1. [动态规划-WIKI](https://zh.wikipedia.org/wiki/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92)
2. [动态规划-OI-WIKI](https://oi-wiki.org/dp/basic/)
3. [动态规划系列](https://labuladong.gitbook.io/algo/dong-tai-gui-hua-xi-lie)