What Is Dynamic Programming?

Remember, don't repeat

Dynamic programming (DP) is for problems where the same smaller problems appear again and again. Solve each one once, store the answer, and reuse it.

Think of it like this: Someone writes 1+1+1+1+1 on a board and you count 5. They add “+1” – you don't recount, you say 6. That's DP.

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

vector<long long> memo(91, -1);

long long fibTop(int n) {                    // top-down
    if (n < 2) return n;
    if (memo[n] != -1) return memo[n];
    return memo[n] = fibTop(n - 1) + fibTop(n - 2);
}

long long fibBottom(int n) {                 // bottom-up
    vector<long long> dp(n + 2, 0);
    dp[1] = 1;
    for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}

int main() {
    cout << fibTop(90) << " " << fibBottom(90) << endl;
    return 0;
}

Output

2880067194370816120 2880067194370816120

The DP recipe

• State: what does dp[i] mean? Say it in words.
• Transition: how is dp[i] built from smaller answers?
• Base case: the answers you know directly.
• Answer: which entry is the final answer?

Remember: DP needs overlapping subproblems and optimal substructure (the best answer is built from best answers to the pieces).