> For the complete documentation index, see [llms.txt](https://haroldyin.gitbook.io/grokking-algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://haroldyin.gitbook.io/grokking-algorithm/chapter-9-dynamic-programming.md).

# Chapter 9: Dynamic Programming

* Every dynamic-programming solution involves a grid.
* The values in the cells are usually what you’re trying to optimize. For the knapsack problem, the values were the value of the goods.
* Each cell is a subproblem, so think about how you can divide your problem into subproblems. That will help you figure out what the axes are.
* Dynamic programming is useful when you’re trying to optimize something given a constraint.
* You can use dynamic programming when the problem can be broken into discrete subproblems.
* Every dynamic-programming solution involves a grid.
* The values in the cells are usually what you’re trying to optimize.
* Each cell is a subproblem, so think about how you can divide your problem into subproblems.
* There’s no single formula for calculating a dynamic-programming solution.

Implementation：

* git diff
* Biologists use the longest common subsequence to find similarities in DNA strands