Dynamic Programming

Welcome to Dynamic Programming

Now that we've covered Sorting and Searching Algorithms, you know how structure and order can make a problem faster. Dynamic Programming, or DP, adds a new idea: when a program keeps solving the same smaller questions, store the answers and reuse them.

In programming terms, DP is not magic. It is a disciplined way to combine:

• the decomposition mindset from Algorithmic Thinking
• the memory choices from Data Structures
• the invariants and contracts from Sorting and Searching Algorithms

By the end of this lesson, you should be able to recognize when a problem has repeated subproblems, define a useful DP state, and implement either a memoized or tabulated C# solution.

When DP Fits

A problem is a good DP candidate when it has two signals:

1. Overlapping subproblems

The same smaller question appears again and again.

Example shape:

Solve(5)
├─ Solve(4)
│  ├─ Solve(3)
│  └─ Solve(2)
└─ Solve(3)   <- repeated

2. Optimal substructure

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

For example, if Best(n) depends on Best(n - 1) and Best(n - 2), then once those smaller answers are known, the larger answer follows.

DP is the moment where your algorithm says: I should not recompute what I already know.

Which task most strongly suggests a Dynamic Programming approach?

Recursive Thinking + Memory

A top-down DP solution starts with a natural recursive definition, then adds a cache.

This style is called memoization:

1. Ask the big question.
2. Recursively ask smaller questions.
3. Before solving, check whether the answer is already cached.
4. Store new answers before returning them.

Here is Fibonacci as a compact example. The point is not Fibonacci itself; it is the pattern of avoiding repeated work.

```csharp
using System;
using System.Collections.Generic;

public class Program
{
    static Dictionary<int, long> memo = new Dictionary<int, long>();

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

        if (memo.ContainsKey(n))
        {
            return memo[n];
        }

        long answer = Fib(n - 1) + Fib(n - 2);
        memo[n] = answer;
        return answer;
    }

    public static void Main()
    {
        int n = 10;
        Console.WriteLine($"Fib({n}) = {Fib(n)}");
        Console.WriteLine($"Cached states: {memo.Count}");
    }
}
```

Fill in the blank:

Top-down Dynamic Programming that stores recursive results in a cache is called ______.

Build From Small To Large

A bottom-up DP solution avoids recursion. Instead, it fills a table in an order where every needed smaller answer is already available.

For the stair problem:

• ways[0] = 1: one way to stay at the ground
• ways[1] = 1: one way to reach step 1
• ways[i] = ways[i - 1] + ways[i - 2]

This is the same relationship as the recursive version, but expressed as a loop.

```csharp
using System;

public class Program
{
    static int CountWays(int n)
    {
        if (n < 0) return 0;

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

        if (n >= 1)
        {
            ways[1] = 1;
        }

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

        return ways[n];
    }

    public static void Main()
    {
        for (int steps = 0; steps <= 6; steps++)
        {
            Console.WriteLine($"Ways to climb {steps} steps: {CountWays(steps)}");
        }
    }
}
```

Dynamic Programming always requires recursion.

The Core Design Move

Most DP solutions become clearer when you name two things:

State

What does one table entry mean?

Example: dp[amount] means the fewest coins needed to make this amount.

Transition

How do smaller states build the current state?

If we try each coin, then:

dp[amount] = min(dp[amount], dp[amount - coin] + 1)

That sentence is your algorithmic invariant: after processing choices, dp[amount] should hold the best known answer for that amount.

```csharp
using System;

public class Program
{
    static int MinCoins(int[] coins, int target)
    {
        int impossible = target + 1;
        int[] dp = new int[target + 1];

        for (int amount = 1; amount <= target; amount++)
        {
            dp[amount] = impossible;
        }

        dp[0] = 0;

        for (int amount = 1; amount <= target; amount++)
        {
            foreach (int coin in coins)
            {
                if (coin <= amount)
                {
                    dp[amount] = Math.Min(dp[amount], dp[amount - coin] + 1);
                }
            }
        }

        return dp[target] == impossible ? -1 : dp[target];
    }

    public static void Main()
    {
        int[] coins = { 1, 3, 4 };
        int target = 6;
        Console.WriteLine($"Minimum coins for {target}: {MinCoins(coins, target)}");
    }
}
```

For the coin example with target amount T and C coin types, what is the time complexity of the shown bottom-up solution?

Your DP Checklist

When you suspect a problem needs Dynamic Programming, use this sequence:

1. Find the repeated question. What subproblem appears many times?
2. Define the state. What does dp[i], dp[i][j], or a memo key represent?
3. Choose base cases. What answers are already known?
4. Write the transition. How do smaller states produce a larger one?
5. Pick direction. Top-down memoization or bottom-up tabulation?
6. Check complexity. How many states exist, and how much work happens per state?

This lesson connects directly to the OODSA habit you've been building: model the problem, choose the right structure, and protect the algorithm with a clear invariant.

Next, we'll move from table-shaped dependencies to relationship-shaped problems in Graph Algorithms.