Dynamic Programming

Why Dynamic Programming Matters

Now that you've finished Recursion and Backtracking, you know how to break a problem into smaller decisions and let the call stack explore them.

Dynamic Programming, usually called DP, is the next upgrade: it teaches you how to avoid solving the same smaller problem again and again.

In interviews, DP often appears when a problem asks for:

• the number of ways to do something
• the best/minimum/maximum result
• whether something is possible
• a sequence decision where today's answer depends on earlier answers

The big idea is simple:

If recursion repeats work, store the result and reuse it.

We'll use Java arrays and recursion concepts you already know, then turn them into efficient interview-ready solutions.

The DP Mental Model

Imagine you're solving fib(5) recursively:

fib(5)
├── fib(4)
│   ├── fib(3)
│   └── fib(2)
└── fib(3)
    ├── fib(2)
    └── fib(1)

Notice the repeated calls: fib(3) and fib(2) appear more than once.

DP is useful when a problem has two properties:

1. Overlapping Subproblems

The same smaller questions appear repeatedly.

Example: fib(3) is needed from multiple paths.

2. Optimal Substructure

The answer to the full problem can be built from answers to smaller problems.

Example: fib(n) = fib(n - 1) + fib(n - 2).

So DP is not a new data structure. It is a problem-solving strategy: define smaller states, solve them once, and reuse them.

Quick Check

Which problem statement most strongly suggests a Dynamic Programming approach?

Top-Down DP: Recursion + Memory

Because you just learned recursion, the most natural DP style is top-down memoization.

The process:

1. Write the recursive solution.
2. Create a cache, often an array or map.
3. Before solving a subproblem, check if it is already cached.
4. Store the answer before returning.

For Fibonacci, the state is just n: the answer to the question, "What is the nth Fibonacci number?"

Without memoization, recursion repeats many calls. With memoization, each n is computed once.

```java
import java.util.Arrays;

public class Main {
    static int calls = 0;

    public static int fib(int n, int[] memo) {
        calls++;

        if (n <= 1) return n;

        if (memo[n] != -1) {
            return memo[n];
        }

        memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
        return memo[n];
    }

    public static void main(String[] args) {
        int n = 10;
        int[] memo = new int[n + 1];
        Arrays.fill(memo, -1);

        int answer = fib(n, memo);
        System.out.println("fib(" + n + ") = " + answer);
        System.out.println("recursive calls = " + calls);
        System.out.println("memo = " + Arrays.toString(memo));
    }
}
```

True or False

Memoization improves a recursive solution by storing answers to subproblems so repeated calls can return immediately.

Bottom-Up DP: Build the Table

The other main DP style is bottom-up tabulation.

Instead of starting from the big problem and recursing downward, you start from the smallest known answers and build upward.

Classic example: climbing stairs.

If you can climb 1 or 2 steps at a time, then to reach step i, your previous move came from:

• step i - 1, or
• step i - 2

So:

dp[i] = dp[i - 1] + dp[i - 2]

Here dp[i] means: number of ways to reach step i.

```java
import java.util.Arrays;

public class Main {
    public static int climbStairs(int n) {
        if (n <= 1) return 1;

        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        System.out.println("dp table: " + Arrays.toString(dp));
        return dp[n];
    }

    public static void main(String[] args) {
        int n = 5;
        System.out.println("ways to climb " + n + " steps = " + climbStairs(n));
    }
}
```

Fill in the Blank

For climbing stairs where you may climb 1 or 2 steps at a time:

dp[i] = __________

Use the standard recurrence.

How to Design a DP Solution

Most DP confusion comes from not knowing what to store.

Use this interview workflow:

1. Define the state

Ask: What smaller question am I answering?

Examples:

• dp[i] = best answer using the first i items
• dp[i] = number of ways to reach position i
• dp[i][j] = answer for prefixes ending at i and j

2. Define the transition

Ask: How does this state use smaller states?

Example:

dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]

3. Define base cases

Ask: What answers are already known?

Example: dp[0], dp[1].

4. Choose direction

Use top-down if recursion feels natural. Use bottom-up if the order is clear and you want tight control over memory.

Example: Minimum Cost Climbing Stairs

Let's solve a common interview-style DP problem.

You are given an array cost, where cost[i] is the cost of stepping on stair i. You can climb 1 or 2 steps at a time. Find the minimum cost to reach the top.

State:

dp[i] = minimum cost to stand on stair i

Transition:

dp[i] = cost[i] + min(dp[i - 1], dp[i - 2])

The top is just beyond the last stair, so the final answer is:

min(dp[n - 1], dp[n - 2])

```java
import java.util.Arrays;

public class Main {
    public static int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n];

        dp[0] = cost[0];
        dp[1] = cost[1];

        for (int i = 2; i < n; i++) {
            dp[i] = cost[i] + Math.min(dp[i - 1], dp[i - 2]);
        }

        System.out.println("cost: " + Arrays.toString(cost));
        System.out.println("dp:   " + Arrays.toString(dp));

        return Math.min(dp[n - 1], dp[n - 2]);
    }

    public static void main(String[] args) {
        int[] cost = {10, 15, 20};
        int answer = minCostClimbingStairs(cost);
        System.out.println("minimum cost = " + answer);
    }
}
```

Your DP Checklist

When a DP problem appears in an interview, slow down and follow the pattern.

Ask these questions

1. What is the state?
   What does dp[i] or dp[i][j] mean?

2. What are the choices?
   From which previous states can I arrive here?

3. What is the recurrence?
   How do I combine smaller answers?

4. What are the base cases?
   Which answers are known without computation?

5. What is the final answer?
   Is it dp[n], dp[n - 1], a max over the table, or something else?

Common beginner mistakes

• Starting code before defining the state
• Forgetting base cases
• Mixing up indexes like i vs i - 1
• Returning the wrong cell from the DP table
• Using DP when there are no repeated subproblems

Next, you'll study Greedy Algorithms, where the mindset changes: instead of storing many subproblem answers, you make the best local choice when that is safe.