Dynamic Programming

The final pattern layer

Now that we've covered Introduction to Data Structures, Recursion, Sliding Windows, and Tree Data Structure, you're ready for a pattern that combines all of them: Dynamic Programming.

DP is not a new data structure. It is a way to organize repeated decisions so your program does not solve the same problem again and again.

Think of it as:

• Recursion gives us the problem breakdown.
• Arrays / Maps store answers to subproblems.
• Traversal order decides when answers become available.
• Cost awareness tells us whether the transformation is worth it.

By the end, you should be able to look at a problem and ask: "Is there a reusable subproblem hiding here?"

When should DP enter your mind?

Dynamic Programming usually fits when a problem has both of these properties:

1. Overlapping subproblems

The same smaller question appears multiple times.

Example: computing fib(5) recursively asks for fib(3) more than once.

2. Optimal substructure

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

Example: the best way to reach step n can be built from the ways to reach n - 1 and n - 2.

The key mental shift

Instead of asking:

"How do I recursively explore everything?"

Ask:

"What subproblem answer can I save and reuse?"

That saved answer is usually stored in an array, matrix, or hash map.

Which problem description is the strongest signal for Dynamic Programming?

Top-down DP: recursion with memory

From the Recursion lesson, you already know how calls break a problem into smaller calls.

Memoization keeps that recursive shape but adds a cache:

1. Define the recursive function.
2. Before solving, check whether the answer is already cached.
3. Store the answer before returning it.

This is often the easiest DP style to write first because it follows the natural problem statement.

Below, fib(6) would normally recompute many values. With memoization, each fib(n) is solved once.

```java
import java.util.*;

public class Main {
    static Map<Integer, Integer> memo = new HashMap<>();

    static int fib(int n) {
        if (n <= 1) return n;

        if (memo.containsKey(n)) {
            return memo.get(n);
        }

        int result = fib(n - 1) + fib(n - 2);
        memo.put(n, result);
        return result;
    }

    public static void main(String[] args) {
        System.out.println("fib(6) = " + fib(6));
        System.out.println("Cached answers: " + memo);
    }
}
```

A DP ______ describes the meaning of one saved subproblem answer, such as dp[i] = number of ways to reach step i.

Bottom-up DP: fill the table intentionally

Tabulation removes recursion and fills answers in an order where dependencies are already known.

For climbing stairs:

• dp[i] = number of ways to reach step i
• To reach i, the previous move came from i - 1 or i - 2
• So: dp[i] = dp[i - 1] + dp[i - 2]

This version is iterative, predictable, and avoids recursion stack depth.

As an experienced Java developer, you can think of this as converting a call graph into a controlled loop over an array.

```java
import java.util.*;

public class Main {
    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 + " stairs = " + climbStairs(n));
    }
}
```

True or false: Every recursive problem should be converted into Dynamic Programming.

The two sentences that solve most DP problems

Before coding, force yourself to write these:

1. State

dp[...] means what?

2. Transition

How do smaller states combine to produce the current state?

Example: count paths in a grid moving only right or down.

• dp[r][c] = number of ways to reach cell (r, c)
• You can arrive from above or from the left
• dp[r][c] = dp[r - 1][c] + dp[r][c - 1]

This is where your earlier lessons connect: the matrix is the data structure, the transition is the pattern, and the loop order is the traversal.

```java
import java.util.*;

public class Main {
    static int uniquePaths(int rows, int cols) {
        int[][] dp = new int[rows][cols];

        for (int r = 0; r < rows; r++) dp[r][0] = 1;
        for (int c = 0; c < cols; c++) dp[0][c] = 1;

        for (int r = 1; r < rows; r++) {
            for (int c = 1; c < cols; c++) {
                dp[r][c] = dp[r - 1][c] + dp[r][c - 1];
            }
        }

        for (int[] row : dp) {
            System.out.println(Arrays.toString(row));
        }

        return dp[rows - 1][cols - 1];
    }

    public static void main(String[] args) {
        System.out.println("Unique paths = " + uniquePaths(3, 4));
    }
}
```

A practical DP checklist

When a problem feels recursive, exponential, or choice-heavy, walk through this checklist:

1. What is the state?

Define exactly what one saved answer means.

Example: dp[i], dp[r][c], dp[index][remaining].

2. What are the base cases?

These are the smallest answers you know without computation.

3. What is the transition?

Write the formula or decision rule.

4. What order fills the answers?

Top-down memoization follows recursion. Bottom-up tabulation needs dependencies filled first.

5. What is the cost?

Usually:

time = number of states × work per state

space = number of stored states

6. Can space be compressed?

If the current state only needs a few previous states, an array may become two variables.

You now have a pattern map

This course started with a simple idea from Introduction to Data Structures: data needs shape, and cost has shape.

Then we built pattern tools:

• Recursion taught you to decompose a problem.
• Sliding Windows taught you to maintain a moving invariant over arrays or strings.
• Tree Data Structure taught you hierarchical modeling and traversal.
• Dynamic Programming taught you to save reusable subproblem answers.

The habit to keep

When facing a coding challenge, do not jump straight to code. First ask:

1. What shape is the data?
2. What operation dominates the cost?
3. Is there a known pattern: recursion, window, traversal, or DP?
4. What invariant or state makes the solution clear?

That is pattern mastering: not memorizing solutions, but recognizing the structure underneath them.