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 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 ...