Dynamic Programming

Dynamic Programming (DP) is a way to solve problems where:

  • The same subproblems repeat many times, and
  • The answer to the big problem can be built from answers to smaller subproblems.

Key idea: Don’t recompute the same thing over and over. Instead, remember (memoize) results in an array or map and reuse them.

Warm-Up: Fibonacci Numbers

We define the Fibonacci sequence:

  • F(0) = 0
  • F(1) = 1
  • F(n) = F(n-1) + F(n-2) for n ≥ 2

Naive Recursive Solution (Slow)

int fib(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fib(n - 1) + fib(n - 2);
}

What’s wrong with this?

  • fib(5) calls fib(4) and fib(3)
  • fib(4) calls fib(3) and fib(2)
  • fib(3) gets called again and again

This creates an exponential number of calls: Time ≈ O(2^n) — too slow for large n.

Fixing It with Memoization (Top-Down DP)

We create an array dp[] where:

  • dp[n] = the value of fib(n) once computed.

Before computing fib(n), we check if it was already computed.

#include <iostream>
#include <vector>
using namespace std;

vector<long long> dp;

long long fib(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;

    if (dp[n] != -1) return dp[n]; // already computed

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

int main() {
    int n = 50;
    dp.assign(n + 1, -1);

    cout << "F(" << n << ") = " << fib(n) << "\n";
}

Now each fib(k) is computed once. All later calls just reuse the stored answer.

SRTBOT Framework for DP

Let’s use SRTBOT to organize our DP thinking:

S – State

What does dp[i] represent?

dp[i] = F(i), the i-th Fibonacci number.

R – Recurrence (Relation)

How do we build big states from smaller ones?

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

T – Transitions (How we move between states)

To compute dp[i], we use:

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

B – Base Cases

We must define the first values:

  • dp[0] = 0
  • dp[1] = 1

O – Order of Computation

For bottom-up DP:

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

We compute from small to large (0 → 1 → 2 → ... → n).

T – Time & Space Complexity

  • Time: each i from 0 to n is computed once → O(n)
  • Space: we store dp[0..n] → O(n) (can be reduced to O(1) by only keeping the last two values)

Minimum Cost to Reach the End

Problem

You are given an array cost[0..n-1], where cost[i] is the energy or money you pay when you step on position i.

You start before the array and want to go beyond the last index (to position n). From index i, you may move to:

  • i + 1, or
  • i + 2

You can start from index 0 or index 1.

Goal: Find the minimum total cost to reach position n.

Example

cost = [1, 100, 1, 1]

Possible ways:

Start at 0:
  0 -> 2 -> n
  cost = cost[0] + cost[2] = 1 + 1 = 2

Start at 1:
  1 -> 3 -> n
  cost = 100 + 1 = 101

Answer = 2

Naive Recursive Solution

Let’s define a recursive function:

  • solve(i) = minimum cost to go from index i to the end (position n).

Transitions:

  • From i, you pay cost[i], then go to i+1 or i+2.
int n;
vector<int> cost;

int solve(int i) {
    if (i >= n) return 0;

    int take1 = solve(i + 1);
    int take2 = solve(i + 2);
    return cost[i] + min(take1, take2);
}

int main() {
    cost = {1, 100, 1, 1};
    n = cost.size();

    int ans = min(solve(0), solve(1));  // can start from 0 or 1
    cout << ans << "\n";
}

Why is this slow?

  • solve(i) calls solve(i+1) and solve(i+2).
  • Those calls overlap heavily (same i recomputed many times).
  • Time becomes exponential in n (O(2^n)).

Add Memoization (Top-Down DP)

We store the answer for each i in dp[i]:

#include <iostream>
#include <vector>
using namespace std;

int n;
vector<int> cost;
vector<int> dp;

int solve(int i) {
    if (i >= n) return 0;

    if (dp[i] != -1) return dp[i]; // already computed

    int take1 = solve(i + 1);
    int take2 = solve(i + 2);
    dp[i] = cost[i] + min(take1, take2);
    return dp[i];
}

int main() {
    cost = {1, 100, 1, 1};
    n = cost.size();
    dp.assign(n, -1);

    int ans = min(solve(0), solve(1));
    cout << "Minimum cost = " << ans << "\n";
}

Now:

  • Each solve(i) is computed once.
  • Total time is O(n) instead of exponential.

Bottom-Up DP Version

We can also do it iteratively from the end to the beginning.

Define:

dp[i] = minimum cost to go from index i to the end.

Then:

  • If i >= n, cost is 0.

  • For i < n:

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

We usually make the array slightly larger (size n+2) to avoid bounds checks.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> cost = {1, 100, 1, 1};
    int n = cost.size();

    vector<int> dp(n + 2, 0); // dp[n] and dp[n+1] = 0 by default

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

    int ans = min(dp[0], dp[1]); // can start from index 0 or 1
    cout << "Minimum cost = " << ans << "\n";
}

SRTBOT for Minimum Cost to Reach the End

Let’s apply the SRTBOT framework.

S – State

dp[i] = minimum total cost to go from index i to position n (i.e., to reach or go beyond the end).

R – Recurrence

From index i, you:

  • Pay cost[i]
  • Then jump to i+1 or i+2

So:

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

T – Transitions

From state i, we can transition to:

  • i + 1
  • i + 2

Those are the only “edges” in our DP graph.

B – Base Cases

We define:

  • dp[n] = 0 (already at/beyond the end, no more cost)
  • dp[n+1] = 0 (safe padding to use dp[i+2] when i = n-1)

In top-down:

  • If i >= n, return 0.

O – Order of Computation

For bottom-up:

  • We process i from n-1 down to 0, so that:

    • dp[i+1] and dp[i+2] are already computed when we calculate dp[i].
for (int i = n - 1; i >= 0; i--) {
    dp[i] = cost[i] + min(dp[i + 1], dp[i + 2]);
}

T – Time & Space Complexity

  • Time: We compute dp[i] once for each i in [0..n-1], each in O(1) → total O(n).

  • Space: We use an array dp of size n+2 → O(n). (We can even reduce it to O(1) by only keeping the last two values.)

Big Picture Intuition for DP

Dynamic Programming usually appears when:

  1. You can write a recursive solution that:

    • Combines answers to smaller subproblems
    • But recomputes the same subproblems many times

  2. You then:

    • Define a state (dp[...])
    • Derive a *ecurrence
    • Add memoization (top-down) or fill a table (bottom-up)

SRTBOT helps you structure your thinking:

State → Recurrence → Transitions → Base cases → Order of computation → Time/space complexity