Introduction to Dynamic Programming

Some problems feel slow no matter how you write the code. You give the computer a small input and it answers fast. You give it a slightly bigger input and it just sits there. The work explodes. Most of the time the reason is simple. Your code keeps solving the same small piece again and again. Dynamic programming is the trick that fixes exactly this.

🤔 What Is Dynamic Programming?

Dynamic programming is a way to solve a big problem. You break it into smaller problems. You solve each small one only once. Then you save that answer so you never have to compute it again.

That last part is the whole point. Solve once. Store the answer. Reuse it later. The small problems are called subproblems. A subproblem is just the same kind of question on a smaller input.

Think of it like homework. Say one question depends on the answer to an earlier question. A smart student writes the earlier answer down on the side. Then when it comes up again, they just read it off the paper. They do not redo the work. Dynamic programming makes the computer do the same thing.

😩 The Pain: Plain Recursion for Fibonacci

Let us look at the classic example. The Fibonacci numbers. Each number is the sum of the two before it. So it goes 0, 1, 1, 2, 3, 5, 8, 13, and so on.

The math rule is short. fib(n) = fib(n-1) + fib(n-2). The first two values are fixed. fib(0) = 0 and fib(1) = 1.

This rule turns into recursion very naturally. A function that calls itself for the two smaller cases.

#include <stdio.h>

// plain recursion: recomputes the same values again and again
int fib(int n) {
    if (n < 2) return n;          // fib(0)=0, fib(1)=1
    return fib(n - 1) + fib(n - 2);
}

int main(void) {
    printf("fib(10) = %d\n", fib(10));
    return 0;
}

fib(10) = 55

#include <iostream>
using namespace std;

// plain recursion: recomputes the same values again and again
int fib(int n) {
    if (n < 2) return n;          // fib(0)=0, fib(1)=1
    return fib(n - 1) + fib(n - 2);
}

int main() {
    cout << "fib(10) = " << fib(10) << endl;
    return 0;
}

fib(10) = 55

public class FibSlow {
    // plain recursion: recomputes the same values again and again
    static int fib(int n) {
        if (n < 2) return n;          // fib(0)=0, fib(1)=1
        return fib(n - 1) + fib(n - 2);
    }

    public static void main(String[] args) {
        System.out.println("fib(10) = " + fib(10));
    }
}

fib(10) = 55

# plain recursion: recomputes the same values again and again
def fib(n):
    if n < 2:          # fib(0)=0, fib(1)=1
        return n
    return fib(n - 1) + fib(n - 2)

print("fib(10) =", fib(10))

fib(10) = 55

// plain recursion: recomputes the same values again and again
function fib(n) {
  if (n < 2) return n;          // fib(0)=0, fib(1)=1
  return fib(n - 1) + fib(n - 2);
}

console.log("fib(10) =", fib(10));

fib(10) = 55

This gives the right answer. The problem is how it gets there. Watch what happens when you ask for fib(5).

See fib(3) showing up twice? And fib(2) shows up over and over. Each one re-opens its own little tree of work below it. Nobody is writing the answer down. So the same small questions get solved again and again.

This is why it explodes. Here is the rough cost as n grows.

🔁 Overlapping Subproblems

The repeated work above has a name. Overlapping subproblems means the same smaller problem comes up many times while you solve the big one.

That is the first signal for dynamic programming. If you ever notice your recursion asking the same question more than once, you have overlapping subproblems.

So what does DP do about it? It is simple.

• Solve each subproblem one time.
• Store its answer in a table or an array.
• The next time that same question comes up, read the stored answer instead of computing it again.

For Fibonacci, that turns all those repeated branches into a single quick lookup. The tree of work collapses into a straight line.

🧱 Optimal Substructure

There is another signal too. Optimal substructure means the best answer to the big problem is built from the best answers to its smaller problems.

For Fibonacci this is clearly true. fib(n) is just fib(n-1) plus fib(n-2). If you have the correct answers to those two smaller pieces, you have the correct answer to the big one. Nothing else is needed.

When both signals show up together, DP fits the problem.

• Overlapping subproblems means storing answers will actually save work.
• Optimal substructure means you can build the big answer from smaller stored answers.

⚡ Before and After on Fibonacci

The fix for Fibonacci is small. Keep an array. Each spot holds one Fibonacci value. Fill them in order, from small to big. Every value gets computed once. After that you just read it when you need it.

Here is the same Fibonacci, but now each value is stored and reused.

#include <stdio.h>

// store each value once, then reuse it
int fib(int n) {
    if (n < 2) return n;          // handles fib(0) and fib(1)
    int dp[n + 1];                // size the array to n
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];   // reuse the two stored answers
    }
    return dp[n];
}

int main(void) {
    printf("fib(10) = %d\n", fib(10));
    return 0;
}

fib(10) = 55

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

// store each value once, then reuse it
int fib(int n) {
    if (n < 2) return n;          // handles fib(0) and fib(1)
    vector<int> dp(n + 1);        // size the array to n
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];   // reuse the two stored answers
    }
    return dp[n];
}

int main() {
    cout << "fib(10) = " << fib(10) << endl;
    return 0;
}

fib(10) = 55

public class FibDp {
    // store each value once, then reuse it
    static int fib(int n) {
        if (n < 2) return n;          // handles fib(0) and fib(1)
        int[] dp = new int[n + 1];    // size the array to n
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];   // reuse the two stored answers
        }
        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println("fib(10) = " + fib(10));
    }
}

fib(10) = 55

# store each value once, then reuse it
def fib(n):
    if n < 2:                    # handles fib(0) and fib(1)
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]   # reuse the two stored answers
    return dp[n]

print("fib(10) =", fib(10))

fib(10) = 55

// store each value once, then reuse it
function fib(n) {
  if (n < 2) return n;          // handles fib(0) and fib(1)
  const dp = new Array(n + 1).fill(0);
  dp[1] = 1;
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];   // reuse the two stored answers
  }
  return dp[n];
}

console.log("fib(10) =", fib(10));

fib(10) = 55

Same answer, 55. But now look at the cost. The loop runs once for each value up to n. No value is ever computed twice.

Here is the difference side by side.

That jump from O(2^n) to O(n) is the whole reason dynamic programming exists. You stopped redoing work.

⚠️ Common Mistakes

A few things trip people up early on. Watch for these.

• Reaching for DP when there is no repeated work. If each subproblem is different, storing answers buys you nothing.
• Forgetting the base cases. For Fibonacci that is fib(0) and fib(1). Without them the recursion never stops.
• Filling the table in the wrong order. A spot must be filled only after the smaller spots it depends on are already filled.
• Thinking DP is one fixed algorithm. It is not. It is just the idea of solving each subproblem once and storing it.

🧩 What You’ve Learned

• ✅ Dynamic programming solves a big problem by breaking it into smaller subproblems, solving each once, and storing the answer.
• ✅ Plain recursion for Fibonacci is slow because it recomputes the same values again and again, costing about O(2^n).
• ✅ Overlapping subproblems means the same smaller question comes up many times, so storing answers saves real work.
• ✅ Optimal substructure means the best big answer is built from the best smaller answers.
• ✅ Storing answers turns Fibonacci from O(2^n) down to O(n). Same result, far less work.

🚀 What’s Next?

• Memoization vs Tabulation
• Fibonacci with DP