Dynamic programming intro

Dynamic programming (DP) solves problems with overlapping subproblems and optimal substructure by storing sub-results—trading space for time. Classic examples: Fibonacci, coin change, knapsack.

Top-down vs bottom-up

• Memoization — recursion + cache (unordered_map or vector)
• Tabulation — fill DP table iteratively from base cases

Fibonacci tabulation

#include 
#include 

int main() {
    int n = 10;
    std::vector dp(n + 1, 0);
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; ++i)
        dp[i] = dp[i - 1] + dp[i - 2];
    std::cout << "F(" << n << ")=" << dp[n] << "\n";
    return 0;
}

DP checklist

1. Define state (what subproblem?)
2. Recurrence relation
3. Base cases
4. Order of computation
5. Answer from table

Important interview questions and answers

1. Q: DP vs divide and conquer?
   A: DP subproblems overlap; D&C subproblems are independent (merge sort).
2. Q: Coin change intuition?
   A: dp[amount] = min coins using dp[amount - coin] + 1—classic unbounded knapsack variant.

Self-check

1. What two properties enable DP?
2. Why naive Fibonacci recursion is O(2^n)?

Tip: Start with brute recursion, add memo, then tabulate—shows clear thinking.