Dynamic Programming: Stop Solving the Same Problem Twice

Dynamic Programming sounds complicated.

It isn’t.

At its core, Dynamic Programming (DP) is about solving a problem once, remembering the answer, and reusing it instead of doing the same work again.

That simple idea can turn an extremely slow algorithm into a very efficient one.

The Problem: Repeated Work

Consider the Fibonacci sequence:

F(n) = F(n - 1) + F(n - 2)

A simple recursive implementation looks like this:

int Fibonacci(int n)
{
    if (n <= 1)
        return n;

    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

It works.

But there is a problem.

To calculate:

F(5)

we calculate F(3) multiple times.

The same thing happens with F(2), F(1), and so on.

As n gets larger, the amount of repeated work grows rapidly.

We're solving the same subproblems over and over again.

That's where Dynamic Programming comes in.

The Core Idea of Dynamic Programming

Dynamic Programming generally follows two ideas:

1. Break a problem into smaller subproblems.
2. Store the results of those subproblems so we can reuse them.

There are two common approaches.

1. Memoization — Top Down

Memoization keeps the recursive approach but stores results that have already been calculated.

int Fibonacci(int n, Dictionary<int, int> memo)
{
    if (n <= 1)
        return n;

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

    memo[n] =
        Fibonacci(n - 1, memo) +
        Fibonacci(n - 2, memo);

    return memo[n];
}

Now, when we need F(3) again, we don't calculate it from scratch.

We simply retrieve the stored result.

Calculate once. Reuse later.

2. Tabulation — Bottom Up

Instead of using recursion, we can build the solution from the smallest subproblems upward.

int Fibonacci(int n)
{
    if (n <= 1)
        return n;

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

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

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

    return dp[n];
}

Here, dp[i] represents the answer to the smaller problem i.

For example:

dp[0] = 0
dp[1] = 1
dp[2] = 1
dp[3] = 2
dp[4] = 3
dp[5] = 5

We're building the answer step by step.

When Should You Think About Dynamic Programming?

A problem is often a good candidate for DP when it has these characteristics:

Overlapping Subproblems

The same smaller problems appear repeatedly.

Fibonacci is the classic example.

Optimal Substructure

The solution to the larger problem can be constructed from solutions to smaller problems.

For example, finding the cheapest way to reach a destination may depend on the cheapest ways to reach previous locations.

When you see "the best way," "the minimum," "the maximum," or "the number of ways", DP should come to mind.

A Simple Real-World Example

Imagine you're climbing a staircase.

You can climb either:

• 1 step
• 2 steps

How many different ways can you reach step n?

To reach step n, your previous step must have been either:

n - 1

or:

n - 2

Therefore:

ways(n) = ways(n - 1) + ways(n - 2)

Notice anything familiar?

It's essentially the Fibonacci pattern.

A DP solution could be:

int ClimbStairs(int n)
{
    if (n <= 2)
        return n;

    int previous = 1;
    int current = 2;

    for (int i = 3; i <= n; i++)
    {
        int next = previous + current;

        previous = current;
        current = next;
    }

    return current;
}

Interestingly, we don't even need to store the entire DP array.

We only need the previous two results.

The DP Pattern to Remember

When approaching a DP problem, ask yourself:

1. What is the smallest version of the problem?

This gives you the base case.

2. What information do I need to remember?

This becomes your DP state.

3. How does the current answer depend on previous answers?

This gives you the recurrence or transition.

4. Can I reuse previously calculated results?

If yes, DP may be the right approach.

Dynamic Programming Isn't Magic

The hardest part of DP usually isn't writing the code.

It's figuring out what the state should represent.

For example:

dp[i]

might mean:

The maximum profit achievable using the first i items.

Or:

dp[i][j]

might mean:

The minimum cost required to reach position (i, j).

Once you can clearly define your state and transition, the implementation often becomes straightforward.

Key Takeaway

Dynamic Programming is essentially smart reuse of previous work.

Instead of repeatedly solving the same subproblem:

Solve → Forget → Solve again

you do:

Solve → Remember → Reuse

So when you encounter a problem with overlapping subproblems and a relationship between smaller and larger solutions, don't immediately reach for brute force.

Ask:

"What have I already calculated that I can reuse?"

That question is often the beginning of a Dynamic Programming solution.