Dynamic Programming Fundamentals

The Mental Model

Dynamic Programming is smart recursion. Instead of solving the same subproblem multiple times, we solve it once and remember the answer. The key insight: if you can express the answer to a problem in terms of answers to smaller problems, DP might work. Analogy: Imagine computing Fibonacci numbers by hand. To get F(50), you need F(49) and F(48). To get F(49), you need F(48) and F(47). Notice F(48) is needed twice—and it explodes from there. Without memoization, computing F(50) requires about 2^50 operations. With memoization (writing each answer on a sticky note the first time you compute it), it takes exactly 50 additions. That is the difference between exponential and linear: DP trades memory for time.

Pattern Recognition Signals:

“Count the number of ways”
“Find minimum/maximum cost”
“Can we achieve X?” (feasibility)
Problem has overlapping subproblems and optimal substructure
Constraints suggest O(n²) or O(n × m) is acceptable

The DP Mindset

When you see a DP problem, think through this framework:

Define the State

What information do I need to describe a subproblem?

dp[i] = answer for first i elements
dp[i][j] = answer for subproblem defined by i and j

Find the Transition

How does dp[i] relate to smaller subproblems?

dp[i] = f(dp[i-1], dp[i-2], …)

Identify Base Cases

What are the simplest subproblems with known answers?

Determine the Order

Which subproblems must be solved before others?

Extract the Answer

Where in the DP table is the final answer?

Pattern 1: Linear DP

State: dp[i] = answer considering first i elements.

Example: Fibonacci

// Recursive (exponential)
int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

// Memoized (top-down DP)
vector<int> memo(n + 1, -1);
int fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    return memo[n] = fib(n - 1) + fib(n - 2);
}

// Tabulation (bottom-up DP)
int fib(int n) {
    if (n <= 1) return n;
    vector<int> dp(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];
}

// Space optimized
int fib(int n) {
    if (n <= 1) return n;
    int prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

Example: Climbing Stairs

Problem: n stairs, can climb 1 or 2 at a time. Count ways to reach top. State: dp[i] = number of ways to reach stair i Transition: dp[i] = dp[i-1] + dp[i-2] (come from i-1 or i-2)

int climbStairs(int n) {
    if (n <= 2) return n;
    vector<int> dp(n + 1);
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

Pattern 2: Coin Change (Unbounded Knapsack)

Problem: Given coins, find minimum coins to make amount. State: dp[i] = minimum coins to make amount i Transition: dp[i] = min(dp[i - coin] + 1) for each coin Worked example: coins = [1, 3, 4], amount = 6

dp[0] = 0
dp[1] = dp[0] + 1 = 1  (use coin 1)
dp[2] = dp[1] + 1 = 2  (use coin 1)
dp[3] = min(dp[2]+1, dp[0]+1) = 1  (use coin 3)
dp[4] = min(dp[3]+1, dp[1]+1, dp[0]+1) = 1  (use coin 4)
dp[5] = min(dp[4]+1, dp[2]+1, dp[1]+1) = 2  (use coin 4 + coin 1)
dp[6] = min(dp[5]+1, dp[3]+1, dp[2]+1) = 2  (use coin 3 + coin 3)
Answer: 2

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, INT_MAX);
    dp[0] = 0;  // Zero coins needed to make amount 0
    
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            // Can we use this coin? (amount >= coin and the remainder is achievable)
            if (coin <= i && dp[i - coin] != INT_MAX) {
                dp[i] = min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    
    return dp[amount] == INT_MAX ? -1 : dp[amount];  // -1 if amount is unreachable
}

Counting Ways

Problem: Count ways to make amount (combinations, not permutations). Critical subtlety: The loop order determines whether you count combinations or permutations.

Coins as outer loop (below): Each coin is considered once in order. Result: combinations. and are counted once.
Amount as outer loop: For each amount, try all coins. Result: permutations. , , and are counted separately.

Most problems ask for combinations. Read carefully!

int countWays(vector<int>& coins, int amount) {
    vector<long long> dp(amount + 1, 0);
    dp[0] = 1;  // One way to make 0: use no coins
    
    // Coins as outer loop: counts COMBINATIONS (not permutations)
    for (int coin : coins) {
        for (int i = coin; i <= amount; i++) {
            dp[i] += dp[i - coin];
        }
    }
    
    return dp[amount];
}
// Example: coins = [1, 2, 3], amount = 4
// Combinations: {1,1,1,1}, {1,1,2}, {2,2}, {1,3} = 4 ways

Codeforces Problems:

Problem	Rating	Link
Coin Combinations I	1500	CSES
Coin Combinations II	1500	CSES

Pattern 3: 0/1 Knapsack

Problem: n items with weight and value. Maximize value in capacity W. Each item used at most once. State: dp[i][w] = max value using first i items with capacity w Transition:

Don’t take item i: dp[i][w] = dp[i-1][w]
Take item i: dp[i][w] = dp[i-1][w - weight[i]] + value[i]

int knapsack(vector<int>& weight, vector<int>& value, int W) {
    int n = weight.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
    
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            dp[i][w] = dp[i - 1][w];  // Don't take
            if (weight[i - 1] <= w) {
                dp[i][w] = max(dp[i][w], 
                               dp[i - 1][w - weight[i - 1]] + value[i - 1]);
            }
        }
    }
    
    return dp[n][W];
}

// Space optimized: O(W) instead of O(n*W)
// Key: iterate capacity BACKWARDS to avoid using same item twice
int knapsack(vector<int>& weight, vector<int>& value, int W) {
    int n = weight.size();
    vector<int> dp(W + 1, 0);
    
    for (int i = 0; i < n; i++) {
        // BACKWARDS: w from W down to weight[i]
        // This ensures dp[w - weight[i]] still holds the value from
        // the PREVIOUS item's row (item i not yet taken at that capacity)
        for (int w = W; w >= weight[i]; w--) {
            dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);
        }
    }
    
    return dp[W];
}

Why Backwards?: If we iterate forwards, we might use item i multiple times (since dp[w - weight[i]] is already updated). Backwards ensures we use the previous row’s values.

Pattern 4: Longest Increasing Subsequence (LIS)

Problem: Find length of longest strictly increasing subsequence. State: dp[i] = length of LIS ending at index i Transition: dp[i] = max(dp[j] + 1) for all j < i where arr[j] < arr[i]

// O(n²) solution
int lis(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1);
    int maxLen = 1;
    
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        maxLen = max(maxLen, dp[i]);
    }
    
    return maxLen;
}

// O(n log n) solution using binary search
int lisOptimized(vector<int>& nums) {
    vector<int> tails;  // tails[i] = smallest ending element for LIS of length i+1
    
    for (int num : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), num);
        if (it == tails.end()) {
            tails.push_back(num);
        } else {
            *it = num;
        }
    }
    
    return tails.size();
}

Key Insight for O(n log n): Maintain the smallest possible tail for each LIS length. Use binary search to find where to place each element. Why this works: tails[i] stores the smallest ending element of all increasing subsequences of length i+1 found so far. This array is always sorted (a longer subsequence must end with a larger value). When a new element arrives, we binary search for where it fits: if it extends the longest subsequence, we append; otherwise, we replace an existing tail with a smaller value, “making room” for future extensions. Walked example: arr = [3, 1, 4, 1, 5, 9, 2, 6]

3: tails = [3]
1: tails = [1] (replace 3—a subsequence of length 1 ending at 1 is better)
4: tails = [1, 4] (extends)
1: tails = [1, 4] (1 is already in position)
5: tails = [1, 4, 5] (extends)
9: tails = [1, 4, 5, 9] (extends)
2: tails = [1, 2, 5, 9] (replace 4—better potential for future extensions)
6: tails = [1, 2, 5, 6] (replace 9)
LIS length = 4

Edge case: The tails array does NOT represent an actual LIS—it stores the best tails. To reconstruct the actual subsequence, you need to track parent pointers during the binary search updates.

Codeforces Problems:

Problem	Rating	Link
Increasing Subsequence	1400	CSES
Towers	1100	CF 37D

Pattern 5: Longest Common Subsequence (LCS)

Problem: Find length of longest common subsequence of two strings. State: dp[i][j] = LCS length of s1[0..i-1] and s2[0..j-1] Transition:

If s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] + 1
Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

int lcs(string& s1, string& s2) {
    int m = s1.size(), n = s2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    
    return dp[m][n];
}

Top-Down vs Bottom-Up

Aspect	Top-Down (Memoization)	Bottom-Up (Tabulation)
Style	Recursive	Iterative
When computed	On demand	All states
Space	Can skip unused states	Computes all
Debug	Stack trace helps	Index-based
Optimization	Harder	Easier (space opt)

Rule of Thumb: Start with top-down (easier to write), convert to bottom-up if needed for optimization.

Contest tip: Top-down memoization is usually faster to code and less error-prone (you do not need to figure out loop order). Use it by default. Switch to bottom-up only when you need space optimization (rolling array) or the recursion depth would cause stack overflow.

Common Mistakes

Mistake 1: Wrong Base Case

// WRONG: dp[0] might need to be 1 for counting problems
dp[0] = 0;

// CORRECT for coin change counting
dp[0] = 1;  // One way to make 0: use no coins

Mistake 2: Integer Overflow

// WRONG for counting problems
int dp[n];

// CORRECT
long long dp[n];
// Or use modular arithmetic
dp[i] = (dp[i] + dp[j]) % MOD;

Mistake 3: Wrong Loop Order

For 0/1 Knapsack with space optimization: iterate capacity backwards
For unbounded knapsack: iterate capacity forwards

Mistake 4: Forgetting States If your DP gives wrong answers, you might be missing state dimensions:

Does order matter? → Might need dp[i][j]
Does parity matter? → Might need dp[i][0/1]

Practice Problems

Beginner (1100-1300)

Problem	Pattern	Link
Dice Combinations	Linear DP	CSES
Frog 1	Linear DP	AtCoder DP A
Vacation	Multi-state	AtCoder DP C

Intermediate (1300-1500)

Problem	Pattern	Link
Book Shop	0/1 Knapsack	CSES
Boredom	Linear DP	CF 455A
Longest Increasing	LIS	CSES

Advanced (1500-1700)

Problem	Pattern	Link
Edit Distance	LCS variant	CSES
Money Sums	Subset sum	CSES
Array Description	DP with constraints	CF 1800

Key Takeaways

State = Subproblem

The DP state must uniquely identify a subproblem.

Transition = Recursion

The transition is how you’d write the recursive relation.

Base Case = Smallest

Base cases are the smallest subproblems with known answers.

Space Optimize

If dp[i] only depends on dp[i-1], you only need O(1) or O(n) space.

Next Up

Chapter 12: DP on Grids & Advanced

Master 2D DP, interval DP, and bitmask DP for more complex problems.

Getting Started

Fundamental Patterns

Greedy & Divide and Conquer