Dynamic programming

Dynamic programming (DP) is an optimization technique used to solve complex problems by breaking them in to smaller subproblems.

We covered some dynamic programming techniques earlier in this book. One problem we solved with dynamic programming was DFS in Chapter 9 , Graphs.

Note

Note that the dynamic programming approach is different from the divide-and-conquer approach (as we used for the merge sort and quick sort algorithms). While the divide and conquer approach breaks the problem into independent subproblems and then combines the solutions, dynamic programming breaks the problem into dependent subproblems.

Another example is the Fibonacci problem we solved in the previous section. We broke the Fibonacci problem into smaller problems, as shown in the diagram of this section.

There are three important steps we need to follow when solving problems with DP:

1. Define the subproblems.
2. Implement the recurrence that solves the subproblems (in this step, we need to follow the steps...