Dynamic Programming

Welcome to Dynamic Programming

Now that we've covered Arrays and Strings, Sorting and Searching, Trees, and Graphs, you're ready for one of the biggest interview topics: Dynamic Programming, usually called DP.

DP is not a new data structure. It is a way to solve problems by:

• breaking a problem into smaller decisions,
• remembering answers you already computed,
• building toward the final answer efficiently.

In finance-style interviews, DP often appears when a problem asks for the best, maximum, minimum, or number of ways under rules.

Think: pricing paths, risk states, trading constraints, route choices, or portfolio-like decisions — but in interview form, usually with arrays, grids, or strings.

When should you suspect DP?

A problem may be a DP problem when it has two ingredients:

1. Repeated subproblems

You keep needing the answer to the same smaller question.

Example:

ways(5) needs ways(4) and ways(3)
ways(4) needs ways(3) and ways(2)

Notice ways(3) appears more than once.

2. A useful relationship

The answer to a bigger problem can be built from smaller answers.

For example:

ways_to_reach_step_i = ways_to_reach_step_(i-1) + ways_to_reach_step_(i-2)

DP turns repeated work into stored work.

Which problem description most strongly suggests a Dynamic Programming approach?

Example: climbing stairs

Suppose you can climb either 1 step or 2 steps at a time.

How many distinct ways are there to reach step n?

To reach step i, your last move must have come from:

• step i - 1, then take 1 step
• step i - 2, then take 2 steps

So:

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

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

This is the core DP habit: define what each stored value means before writing code.

```python
def climb_stairs(n):
    if n <= 1:
        return 1

    dp = [0] * (n + 1)
    dp[0] = 1  # one way to stand at the bottom: do nothing
    dp[1] = 1  # one way to reach step 1

    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    print("DP table:", dp)
    return dp[n]

print("Ways to climb 5 steps:", climb_stairs(5))
```

True or false?

In the climbing stairs example, dp[i] stores the number of ways to reach exactly step i.

DP is not only counting

DP can also find a minimum or maximum.

Example: each stair has a cost. You can climb 1 or 2 steps at a time. What is the minimum cost to reach each step?

For step i, you could arrive from:

• i - 1
• i - 2

So choose the cheaper previous path:

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

This is common in interviews: a problem gives you choices, and DP stores the best result after each choice.

```python
def min_cost_to_step(cost):
    n = len(cost)
    if n == 0:
        return 0
    if n == 1:
        return cost[0]

    dp = [0] * n
    dp[0] = cost[0]
    dp[1] = cost[1]

    for i in range(2, n):
        dp[i] = cost[i] + min(dp[i - 1], dp[i - 2])

    print("Costs:", cost)
    print("Minimum cost table:", dp)
    return min(dp[n - 1], dp[n - 2])

print("Minimum cost to reach the top:", min_cost_to_step([10, 15, 20, 5]))
```

In the climbing stairs problem, fill in the recurrence:

dp[i] = ______

Use the exact expression for combining the previous two answers.

Do we always need the whole table?

Not always.

In climbing stairs, each answer only needs the previous two answers:

dp[i - 1]
dp[i - 2]

So instead of storing the entire array, we can keep two variables.

This is a useful interview upgrade:

• table version: O(n) time, O(n) space
• optimized version: O(n) time, O(1) space

This connects back to Time and Space Complexity Analysis: same time, less memory.

```python
def climb_stairs_optimized(n):
    if n <= 1:
        return 1

    two_back = 1  # ways to reach step 0
    one_back = 1  # ways to reach step 1

    for i in range(2, n + 1):
        current = one_back + two_back
        two_back = one_back
        one_back = current
        print(f"step {i}: {current} ways")

    return one_back

print("Answer:", climb_stairs_optimized(6))
```

A simple DP thinking loop

When you see a DP-style problem, do not start coding immediately. Use this checklist:

1. Define the state

What does dp[i], dp[row][col], or another stored value mean?

2. Choose base cases

What answers are already obvious?

Examples:

• dp[0] = 1
• first row of a grid
• empty prefix of a string

3. Find the transition

How do smaller answers combine into a bigger answer?

4. Pick an order

Can you fill left-to-right? Top-to-bottom? Smaller length to larger length?

5. Analyze complexity

Use the tools from Time and Space Complexity Analysis.

If your table has n cells and each cell takes O(1) work, the solution is usually O(n).

What you should remember

Dynamic Programming is mainly about organized memory.

You are saying:

If I can solve smaller versions once, I should reuse those answers instead of recomputing them.

For interviews, focus on explaining your thought process clearly:

State:       What does each dp value mean?
Base case:   What do I know immediately?
Transition:  How do previous answers create this one?
Order:       In what order can I safely fill values?
Complexity:  How much time and space?

Next, we will move to a different low-level tool: Bit Manipulation. DP was about remembering structured choices; bit manipulation is about representing information compactly.