> ## Documentation Index
> Fetch the complete documentation index at: https://resources.devweekends.com/llms.txt
> Use this file to discover all available pages before exploring further.

# Dynamic Programming Fundamentals

> Master the most powerful technique in competitive programming—state design, transitions, and the DP mindset

# Dynamic Programming Fundamentals

<img src="https://mintcdn.com/devweeekends/AEOaWh79Ur7CdHHv/images/courses/cp/dp-state-transition.svg?fit=max&auto=format&n=AEOaWh79Ur7CdHHv&q=85&s=0ed367012af16d7c9a16748493844274" alt="DP State Transition Visualization" width="1080" height="1080" data-path="images/courses/cp/dp-state-transition.svg" />

## 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.

<Note>
  **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
</Note>

***

## The DP Mindset

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

<Steps>
  <Step title="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
  </Step>

  <Step title="Find the Transition">
    How does dp\[i] relate to smaller subproblems?

    * dp\[i] = f(dp\[i-1], dp\[i-2], ...)
  </Step>

  <Step title="Identify Base Cases">
    What are the simplest subproblems with known answers?
  </Step>

  <Step title="Determine the Order">
    Which subproblems must be solved before others?
  </Step>

  <Step title="Extract the Answer">
    Where in the DP table is the final answer?
  </Step>
</Steps>

***

## Pattern 1: Linear DP

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

### Example: Fibonacci

```cpp theme={null}
// 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)

```cpp theme={null}
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
```

```cpp theme={null}
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. {1,1,2} and {2,1,1} are counted once.
* **Amount as outer loop**: For each amount, try all coins. Result: permutations. {1,1,2}, {1,2,1}, and {2,1,1} are counted separately.

Most problems ask for combinations. Read carefully!

```cpp theme={null}
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](https://cses.fi/problemset/task/1635) |
| Coin Combinations II | 1500   | [CSES](https://cses.fi/problemset/task/1636) |

***

## 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]

```cpp theme={null}
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];
}
```

<Warning>
  **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.
</Warning>

***

## 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]

```cpp theme={null}
// 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

<Warning>
  **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.
</Warning>

**Codeforces Problems**:

| Problem                | Rating | Link                                                     |
| ---------------------- | ------ | -------------------------------------------------------- |
| Increasing Subsequence | 1400   | [CSES](https://cses.fi/problemset/task/1145)             |
| Towers                 | 1100   | [CF 37D](https://codeforces.com/problemset/problem/37/D) |

***

## 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])

```cpp theme={null}
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.

<Tip>
  **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.
</Tip>

***

## Common Mistakes

<Warning>
  **Mistake 1: Wrong Base Case**

  ```cpp theme={null}
  // 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
  ```
</Warning>

<Warning>
  **Mistake 2: Integer Overflow**

  ```cpp theme={null}
  // WRONG for counting problems
  int dp[n];

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

<Warning>
  **Mistake 3: Wrong Loop Order**

  * For 0/1 Knapsack with space optimization: iterate capacity backwards
  * For unbounded knapsack: iterate capacity forwards
</Warning>

<Warning>
  **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]
</Warning>

***

## Practice Problems

### Beginner (1100-1300)

| Problem           | Pattern     | Link                                                      |
| ----------------- | ----------- | --------------------------------------------------------- |
| Dice Combinations | Linear DP   | [CSES](https://cses.fi/problemset/task/1633)              |
| Frog 1            | Linear DP   | [AtCoder DP A](https://atcoder.jp/contests/dp/tasks/dp_a) |
| Vacation          | Multi-state | [AtCoder DP C](https://atcoder.jp/contests/dp/tasks/dp_c) |

### Intermediate (1300-1500)

| Problem            | Pattern      | Link                                                       |
| ------------------ | ------------ | ---------------------------------------------------------- |
| Book Shop          | 0/1 Knapsack | [CSES](https://cses.fi/problemset/task/1158)               |
| Boredom            | Linear DP    | [CF 455A](https://codeforces.com/problemset/problem/455/A) |
| Longest Increasing | LIS          | [CSES](https://cses.fi/problemset/task/1145)               |

### Advanced (1500-1700)

| Problem           | Pattern             | Link                                                        |
| ----------------- | ------------------- | ----------------------------------------------------------- |
| Edit Distance     | LCS variant         | [CSES](https://cses.fi/problemset/task/1639)                |
| Money Sums        | Subset sum          | [CSES](https://cses.fi/problemset/task/1745)                |
| Array Description | DP with constraints | [CF 1800](https://codeforces.com/problemset/problem/1800/C) |

***

## Key Takeaways

<CardGroup cols={2}>
  <Card title="State = Subproblem" icon="database">
    The DP state must uniquely identify a subproblem.
  </Card>

  <Card title="Transition = Recursion" icon="arrow-right">
    The transition is how you'd write the recursive relation.
  </Card>

  <Card title="Base Case = Smallest" icon="minimize">
    Base cases are the smallest subproblems with known answers.
  </Card>

  <Card title="Space Optimize" icon="minimize">
    If dp\[i] only depends on dp\[i-1], you only need O(1) or O(n) space.
  </Card>
</CardGroup>

***

## Next Up

<Card title="Chapter 12: DP on Grids & Advanced" icon="arrow-right" href="/courses/competitive-programming/12-dp-grids-intervals">
  Master 2D DP, interval DP, and bitmask DP for more complex problems.
</Card>