Dynamic Programming: Fill a Table

Remember small answers to build big ones

In Module 6 you made Fibonacci fast with a memo. That's the heart of dynamic programming (DP): a big problem is built from smaller overlapping problems, so you solve each small one once and store it.

Bottom-up Fibonacci

public class Main {
    public static void main(String[] args) {
        int n = 50;
        long[] dp = new long[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];    // each answer from the two before it
        }
        System.out.println("fib(10) = " + dp[10]);
        System.out.println("fib(50) = " + dp[50]);
    }
}

Output

fib(10) = 55
fib(50) = 12586269025

No recursion, no stack overflow, O(n) time.

The DP recipe

1. Define what dp[i] means in words. (This is the hardest and most important step.)
2. Base cases: the smallest answers you know directly.
3. Rule: how dp[i] is built from smaller entries.
4. Order: fill the table so the entries you need are already done.
5. Answer: which entry holds the final result.

Think of it like this: Climbing stairs and writing on each step how many ways there are to reach it. To fill step 10 you just look at the numbers already written on steps 9 and 8.

Remember: Use DP when a problem asks for the best (min/max) or the number of ways, and the same smaller questions keep coming back.