Dynamic programming is useful when a problem has overlapping subproblems: the program keeps solving the same smaller question again and again. The fix is to save answers and reuse them.
From slow recursion to memoization
The classic recursive Fibonacci method repeats work. fib(6) asks for fib(5) and fib(4). Then fib(5) asks for fib(4) again.
public static int fib(int n, int[] memo)
{
if (n <= 1)
return n;
if (memo[n] != 0)
return memo[n];
memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
return memo[n];
}The array stores answers after they are computed. Future calls return immediately. The runtime changes from exponential growth to linear growth for this version.
Harder example: best total up stairs
Suppose each stair has points, and a student can move 1 or 2 stairs at a time. What is the best total score to reach each stair?
public static int bestScore(int[] points)
{
if (points.length == 0)
return 0;
int[] dp = new int[points.length];
dp[0] = points[0];
if (points.length > 1)
dp[1] = points[1] + Math.max(0, dp[0]);
for (int i = 2; i < points.length; i++)
{
dp[i] = points[i] + Math.max(dp[i - 1], dp[i - 2]);
}
return dp[points.length - 1];
}The state is dp[i]: the best score ending at stair i. The transition chooses the better previous place: one step back or two steps back. Students should write this sentence before writing code.
Memoization vs tabulation
- Memoization: start with recursion, save answers as needed.
- Tabulation: build a table from the smallest cases upward.
- State: what one table entry means.
- Transition: how earlier answers create the next answer.
Common traps
- Starting code before defining the state.
- Forgetting base cases in the table.
- Using a memo default value that could also be a real answer.
- Applying dynamic programming when a simple greedy or sorting solution is enough.
Practice prompt
Write the state and transition for: "How many ways can a student earn exactly n points using 2-point, 3-point, and 7-point tasks?" Then compute the table by hand for n from 0 through 10.