13 — Dynamic Programming (1D)

Neetcode Week 11. DP is the topic that scares people, but it's just structured recursion + memoization. The hardest part is recognizing a problem as DP and defining the state. This file builds intuition through 1D DP.

Table of Contents

1. What DP really is
2. The two flavors: top-down vs bottom-up
3. How to recognize a DP problem
4. How to design a DP solution (5-step framework)
5. Pattern: Fibonacci-style (linear recurrence)
6. Pattern: Decision DP (House Robber, Stock variants)
7. Pattern: Coin Change family
8. Pattern: Subsequence DP (LIS)
9. Pattern: Partition / Word-Break DP
10. Pattern: Palindromic substrings
11. Pitfalls
12. Practice list

---

1. What DP really is

DP solves problems with two properties:

1. Optimal substructure — the optimal solution to the whole problem contains optimal solutions to subproblems.
2. Overlapping subproblems — the same subproblem comes up many times.

If only (1) but not (2), it's divide-and-conquer, not DP. If (2) but not (1), it's just enumeration.

When both hold, cache the results of each subproblem. We trade space for time, going from exponential to polynomial.

Example: Fibonacci

Naive:                                    Memoized:
fib(5)                                    fib(5)
├── fib(4)                                ├── fib(4)
│   ├── fib(3)                            │   ├── fib(3)
│   │   ├── fib(2)                        │   │   ├── fib(2) → compute, cache
│   │   │   ├── fib(1)                    │   │   └── fib(1) → cache hit
│   │   │   └── fib(0)                    │   └── fib(2) → cache hit
│   │   └── fib(1)                        └── fib(3) → cache hit
│   └── fib(2)
│       ├── fib(1)                        Number of unique subproblems = n+1
│       └── fib(0)                        Time = O(n)
└── fib(3)
    ├── fib(2)
    │   ├── fib(1)
    │   └── fib(0)
    └── fib(1)

2^n calls

The naive version recomputes fib(2) exponentially many times. The memoized version computes each once.

---

2. The two flavors

Top-down (memoization)

Write the recursion, then add a cache.

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2: return n
    return fib(n - 1) + fib(n - 2)

Or manually:

def fib(n, memo=None):
    if memo is None: memo = {}
    if n < 2: return n
    if n in memo: return memo[n]
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

Pros: straightforward to derive; only computes states actually needed. Cons: call-stack overhead; recursion depth limits.

Bottom-up (tabulation)

Build a table from base cases up.

def fib(n):
    if n < 2: return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

Pros: no recursion overhead; easier to optimize space. Cons: must explicitly identify the iteration order.

Space optimization

Often you only need the last few states. For Fibonacci:

def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

O(1) space! Many DPs allow this when the recurrence only depends on a constant window.

Which to use in interview?

• Start with top-down to understand the problem (it follows directly from recursive structure).
• Convert to bottom-up if the interviewer pushes for it or if you need O(1) space.

---

3. How to recognize a DP problem

DP triggers in problem statements:

• "Find the number of ways..." — counting; usually DP.
• "Find the minimum / maximum cost / length of..." — optimization; often DP.
• "Can you achieve X?" — feasibility; often DP.
• "Given choices and constraints..." — combinatorial; often DP.

NOT DP if:

• "Find any one X" — could be greedy or BFS.
• "Find all X" — backtracking.
• "Sort / search" — different category.

DP often shows up disguised as:

• Robber problems (decide-include-or-skip).
• Stock problems (decide-buy-or-sell).
• Knapsack (pick items with constraints).
• Strings (LCS, edit distance).
• Grids (paths from corner to corner).

---

4. How to design a DP solution

The 5-step framework:

Step 1: Identify the state

What variables uniquely determine a subproblem? Examples:

• Fibonacci: n
• House Robber: index i
• Coin Change: amount a
• LIS: ending index i

Step 2: Define dp[state]

What does dp mean? E.g.,

• dp[i] = max money from houses 0..i-1.
• dp[a] = min coins to make amount a.

This is the most error-prone step. Write down the meaning in plain English before coding.

Step 3: Recurrence

Express dp[state] in terms of smaller states.

dp[i] = max(dp[i-1], dp[i-2] + nums[i])      # House Robber
dp[a] = 1 + min(dp[a - c] for c in coins)     # Coin Change

Step 4: Base case

Smallest state(s):

dp[0] = 0; dp[1] = nums[0]   # House Robber
dp[0] = 0                     # Coin Change

Step 5: Iteration order (for bottom-up)

The order must satisfy: when computing dp[state], all dependencies are already computed.

• Linear: i from low to high.
• 2D: rows then cols, or sometimes diagonal.

---

5. Pattern: Fibonacci-style

Climbing Stairs (Easy)

Each step, climb 1 or 2 stairs. How many ways to reach n?

State: dp[i] = ways to reach step i. Recurrence: dp[i] = dp[i-1] + dp[i-2] (came from one or two below). Base: dp[0] = 1, dp[1] = 1.

def climb_stairs(n):
    if n <= 2: return n
    a, b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b

Min Cost Climbing Stairs (Easy)

cost[i] = pay to step on stair i. Reach top from index 0 or 1. Minimum total cost?

def min_cost(cost):
    a, b = 0, 0                                # cost to reach idx 0 and 1
    for i in range(2, len(cost) + 1):
        a, b = b, min(a + cost[i-2], b + cost[i-1])
    return b

---

6. Pattern: Decision DP

"At each step, choose to include or skip."

House Robber (Medium)

Adjacent houses can't both be robbed. Max total?

State: dp[i] = max from houses 0..i-1. Recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i-1]). Base: dp[0] = 0, dp[1] = nums[0].

def rob(nums):
    prev2 = prev1 = 0
    for n in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + n)
    return prev1

House Robber II (Medium) — circular

Houses arranged in circle: first and last are adjacent.

Trick: rob is either uses house 0 or doesn't. Run the regular House Robber on nums[:-1] (excludes last) and on nums[1:] (excludes first); take max.

def rob2(nums):
    if len(nums) == 1: return nums[0]
    def rob_linear(arr):
        prev2 = prev1 = 0
        for n in arr:
            prev2, prev1 = prev1, max(prev1, prev2 + n)
        return prev1
    return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))

Buy/Sell Stock with Cooldown (Medium)

Profit from any number of buy/sell, but must wait 1 day after sell.

State: dp[i] = max profit at end of day i, by mode.

• hold[i] = max profit with stock in hand on day i.
• sold[i] = max profit with no stock, just sold on day i.
• rest[i] = max profit with no stock, on cooldown or idle.

Recurrence:

• hold[i] = max(hold[i-1], rest[i-1] - prices[i]) (keep, or buy after cooldown)
• sold[i] = hold[i-1] + prices[i]
• rest[i] = max(rest[i-1], sold[i-1])

def max_profit(prices):
    hold, sold, rest = -prices[0], 0, 0
    for p in prices[1:]:
        prev_hold, prev_sold, prev_rest = hold, sold, rest
        hold = max(prev_hold, prev_rest - p)
        sold = prev_hold + p
        rest = max(prev_rest, prev_sold)
    return max(sold, rest)

This state-machine DP generalizes to all stock variants. Define states for "in / out / cooldown" and transitions between them.

---

7. Pattern: Coin Change family

Coin Change (Medium)

Min coins to make amount n. -1 if impossible.

State: dp[a] = min coins to make amount a. Recurrence: dp[a] = 1 + min(dp[a - c] for c in coins if a >= c). Base: dp[0] = 0.

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

Complexity: O(amount × len(coins)).

Coin Change II (Medium) — number of ways

How many distinct combinations make amount? (Order doesn't matter.)

Trick: outer loop over coins, inner over amount — this enforces "use coins in order" so we don't double-count [1,2] and [2,1].

def change(amount, coins):
    dp = [0] * (amount + 1)
    dp[0] = 1
    for c in coins:
        for a in range(c, amount + 1):
            dp[a] += dp[a - c]
    return dp[amount]

If you swap the loop order, you'll count combinations with order, like permutations — wrong answer.

---

8. Pattern: Subsequence DP

Longest Increasing Subsequence (Medium)

[10, 9, 2, 5, 3, 7, 101, 18] → 4 (LIS = [2, 3, 7, 101]).

State: dp[i] = length of LIS ending at index i. Recurrence: dp[i] = 1 + max(dp[j] for j < i if nums[j] < nums[i]).

def length_of_lis(nums):
    n = len(nums)
    dp = [1] * n
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

Complexity: O(n²).

O(n log n) LIS using patience sort + binary search

import bisect

def length_of_lis(nums):
    tails = []
    for x in nums:
        idx = bisect.bisect_left(tails, x)
        if idx == len(tails):
            tails.append(x)
        else:
            tails[idx] = x
    return len(tails)

tails[i] = smallest possible tail of an LIS of length i+1. Tracks LIS length only (not the actual sequence).

This is a Google favorite.

---

9. Pattern: Partition DP

Word Break (Medium)

Can s be segmented into a sequence of words from wordDict?

State: dp[i] = True if s[:i] can be segmented. Recurrence: dp[i] = any(dp[j] and s[j:i] in word_set for j in range(i)).

def word_break(s, wordDict):
    word_set = set(wordDict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break
    return dp[n]

Optimization: only j values such that i - j ≤ max_word_len need checking. Saves time when words are short.

Partition Equal Subset Sum (Medium)

Can nums be partitioned into two subsets with equal sums? Equivalent to: subset sums to total / 2.

State: dp[t] = True if some subset sums to t. Recurrence: for each num, dp[t] = dp[t] or dp[t - num] (iterate t from high to low).

def can_partition(nums):
    total = sum(nums)
    if total % 2: return False
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True
    for num in nums:
        for t in range(target, num - 1, -1):
            dp[t] = dp[t] or dp[t - num]
    return dp[target]

This is the 0/1 Knapsack decision variant. See 14-dp-2d.md for full knapsack.

---

10. Pattern: Palindromic substrings

Longest Palindromic Substring (Medium)

"babad" → "bab" (or "aba").

Expand around center — O(n²) and conceptually simple:

def longest_palindrome(s):
    if not s: return ""
    start, max_len = 0, 1
    
    def expand(l, r):
        nonlocal start, max_len
        while l >= 0 and r < len(s) and s[l] == s[r]:
            if r - l + 1 > max_len:
                start, max_len = l, r - l + 1
            l -= 1; r += 1
    
    for i in range(len(s)):
        expand(i, i)        # odd-length palindrome
        expand(i, i + 1)    # even-length palindrome
    return s[start:start + max_len]

The DP version (state dp[i][j] = is s[i:j+1] a palindrome) is also O(n²) but uses more memory. Most interviewers accept expand-around-center.

Palindromic Substrings (Medium) — count

def count_substrings(s):
    count = 0
    for i in range(len(s)):
        l, r = i, i
        while l >= 0 and r < len(s) and s[l] == s[r]:
            count += 1; l -= 1; r += 1
        l, r = i, i + 1
        while l >= 0 and r < len(s) and s[l] == s[r]:
            count += 1; l -= 1; r += 1
    return count

Decode Ways (Medium)

"12" → 2 ways: "AB", "L". "226" → 3.

State: dp[i] = ways to decode s[:i]. Recurrence:

• One-digit: dp[i] += dp[i-1] if s[i-1] != '0'.
• Two-digit: dp[i] += dp[i-2] if '10' <= s[i-2:i] <= '26'.

def num_decodings(s):
    if s[0] == '0': return 0
    n = len(s)
    a, b = 1, 1                                  # dp[i-2], dp[i-1]
    for i in range(2, n + 1):
        c = 0
        if s[i-1] != '0':
            c += b
        two = int(s[i-2:i])
        if 10 <= two <= 26:
            c += a
        a, b = b, c
    return b

Maximum Subarray (Kadane's Algorithm — Medium)

Largest contiguous sum.

State: dp[i] = max sum of subarray ending at i. Recurrence: dp[i] = max(nums[i], dp[i-1] + nums[i]).

def max_subarray(nums):
    cur = best = nums[0]
    for n in nums[1:]:
        cur = max(n, cur + n)
        best = max(best, cur)
    return best

The classic. Memorize.

Maximum Product Subarray (Medium)

Like Kadane, but for product. Trick: track both min and max ending at i, since multiplying by a negative flips them.

def max_product(nums):
    cur_max = cur_min = best = nums[0]
    for n in nums[1:]:
        if n < 0:
            cur_max, cur_min = cur_min, cur_max
        cur_max = max(n, cur_max * n)
        cur_min = min(n, cur_min * n)
        best = max(best, cur_max)
    return best

---

11. Pitfalls

Off-by-one in indexing dp

dp[i] could mean:

• "Considering first i elements" (so dp has n+1 entries; dp[0] is empty).
• "Ending at index i" (so dp has n entries).

State your meaning explicitly. Both are valid; mixing them creates bugs.

Wrong iteration order

For 0/1 Knapsack, you must iterate t backward to avoid using the same item twice. For Coin Change II (unbounded), t goes forward.

Forgetting base cases

dp[0] (empty input) and dp[1] (single element) are tricky. Make sure they make sense. E.g., for "min coins for amount 0," answer is 0 (use no coins).

Mutating cached state in top-down

@lru_cache
def f(state, choices):
    choices.append(...)         # ← BAD: mutating arg invalidates cache

Use immutable args (tuple, frozenset).

Missing dimensions

If your state needs more than one variable (e.g., index + remaining money), 1D DP isn't enough. See 14-dp-2d.md.

Greedy when DP needed

"Coin Change" — greedy works for US coins but not arbitrary denominations. Always verify or just use DP.

---

12. Practice list

#	Problem	Pattern	Difficulty
70	Climbing Stairs	Fibonacci	Easy
746	Min Cost Climbing Stairs	Fibonacci	Easy
198	House Robber	Decision	Medium
213	House Robber II	Circular decision	Medium
5	Longest Palindromic Substring	Expand around center	Medium
647	Palindromic Substrings	Expand around center	Medium
91	Decode Ways	Step-DP	Medium
322	Coin Change	Bottom-up	Medium
152	Maximum Product Subarray	Track min+max	Medium
53	Maximum Subarray	Kadane	Medium
139	Word Break	Partition	Medium
300	Longest Increasing Subsequence	Subseq DP	Medium
416	Partition Equal Subset Sum	0/1 knapsack	Medium
309	Best Time Buy/Sell with Cooldown	State machine	Medium

---

TL;DR ✅

• DP = optimal substructure + overlapping subproblems. Cache to avoid recomputing.
• Top-down (memo) = recursive + cache. Bottom-up (table) = iterative.
• Five steps: state, definition, recurrence, base case, iteration order.
• Fibonacci-style for stair / robber problems.
• Coin change (min) and Coin change II (count) — different loop orders matter.
• LIS in O(n log n) with patience-sort + binary search.
• Kadane = O(n) max subarray. Max product = track both min and max.
• Expand around center is the cleanest palindrome substring solution.

Next: 14-dp-2d.md.

External resources

• NeetCode 1D DP playlist: https://www.youtube.com/playlist?list=PLot-Xpze53lcvx_tjrr_m2lgD2NsRHlNO
• Errichto DP tutorial: https://www.youtube.com/watch?v=YBSt1jYwVfU
• "How to think recursively" (DP introduction): https://leetcode.com/discuss/general-discussion/458695/dynamic-programming-patterns