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