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

# 动态规划算法

### 小结

1. 需要在给定约束条件下优化某种指标时，动态规划很有用。
2. 问题可分解为离散子问题时，可使用动态规划来解决。
3. 每种动态规划解决方案都涉及网格。
4. 单元格中的值通常就是你要优化的值。
5. 每个单元格都是一个子问题，因此你需要考虑如何将问题分解为子问题。
6. 没有放之四海皆准的计算动态规划解决方案的公式。

###  应用场景

1. 生物学家根据最长公共序列来确定DNA链的相似性，进而判断度两种动物或疾病有多相 似。最长公共序列还被用来寻找多发性硬化症治疗方案。 
2. 你使用过诸如git diff等命令吗？它们指出两个文件的差异，也是使用动态规划实现的。 
3. 前面讨论了字符串的相似程度。编辑距离（levenshtein distance）指出了两个字符串的相 似程度，也是使用动态规划计算得到的。编辑距离算法的用途很多，从拼写检查到判断 用户上传的资料是否是盗版，都在其中。 
4. 你使用过诸如Microsoft Word等具有断字功能的应用程序吗？它们如何确定在什么地方断字以确保行长一致呢？使用动态规划！
5. 旅游行程最优化，在有限的时间里获得最好的旅游体验。

学习动态规划，这是一种解决棘手问题的方法，它将问题分成小问题，并先着手解决这 些小问题。

### Python代码实现