Using Fibonacci to illustrate memoization and tabulation, and solving the classic 0/1 Knapsack problem.
The Fibonacci sequence is the quintessential example for introducing Dynamic Programming. A naive recursive solution `fib(n) = fib(n-1) + fib(n-2)` has an exponential time complexity because it repeatedly calculates the same Fibonacci numbers. This demonstrates the 'overlapping subproblems' property perfectly. We can optimize this dramatically using DP. The top-down approach, memoization, uses a lookup table (e.g., an array) to store the results of `fib(k)` as they are computed. Before computing `fib(k)`, it checks if the result is already in the table. The bottom-up approach, tabulation, fills the table iteratively, starting from `fib(0)` and `fib(1)` and building up to `fib(n)`. The 0/1 Knapsack problem is a classic optimization problem. Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. The '0/1' property means that for each item, you can either take it or leave it. This problem exhibits optimal substructure and is solved using a 2D DP table `dp[i][w]`, representing the maximum value achievable with the first `i` items and a weight capacity of `w`.