Understanding Dynamic Programming through Staircase and Knapsack Examples

In a conversational format, the tutor introduces dynamic programming by first asking the student what comes to mind when hearing the term, then guiding them through a classic staircase problem where each step can be taken one or two stairs at a time.

The tutor demonstrates that the number of ways to reach step F(x) = F(x-1) + F(x-2) , with base cases F(1)=1 and F(2)=2 , forms the Fibonacci sequence. An initial recursive solution is shown:

int getWays(int n) { if (n == 1) { return 1; } if (n == 2) { return 2; } return getWays(n-1) + getWays(n-2); }

The tutor points out the exponential time complexity O(2^n) and introduces an optimized iterative version that stores only the two previous values, achieving O(N) time and O(1) space:

int getWays2(int n) { if (n == 1) { return 1; } if (n == 2) { return 2; } int a = 1; int b = 2; int temp = 0; for (int i = 3; i <= n; i++) { temp = a + b; a = b; b = temp; } return temp; }

Next, the tutor shifts to the 0/1 knapsack problem with a 5 kg capacity and four items, guiding the student to define the DP state F(W,i) as the maximum value achievable with weight limit W using the first i items.

The state transition is derived as F(W,i) = max{ F(W-w_i, i-1) + v_i , F(W, i-1) } , with optimal substructure, boundary conditions (e.g., F(0,*) = 0 , F(*,0) = 0 ), and a table-filling illustration that leads to the final optimal value.

Throughout, the dialogue emphasizes the three key DP components—optimal substructure, state transition equation, and boundary values—illustrating how to abstract specific numeric examples into general formulas.