Sign inSign up
Back to Problems
BacktrackingGreedy
PATTERN 14 OF 22

Dynamic Programming (1D)

Solve optimization and counting problems by breaking them into overlapping subproblems, storing results to avoid recomputation. Master the 3-step recipe: define state, write recurrence, set base cases. Covers Fibonacci-style, take/skip, knapsack, subsequence, and subarray archetypes.

Time: O(n) for Fibonacci/take-skip, O(n·k) for knapsack, O(n²) for subsequence
Space: O(n) for DP array, O(1) with space optimization for Fibonacci/take-skip

Learn & Reference

Understanding the Pattern

Dynamic Programming (1D) Pattern

Dynamic Programming (DP) is an optimization technique for problems with two key properties:

  1. Overlapping subproblems — the same smaller problem is solved multiple times
  2. Optimal substructure — the optimal solution builds from optimal solutions to subproblems
Fibonacci without DP:               With DP (bottom-up):
fib(5)                               dp[0] = 0
 ├─ fib(4)                            dp[1] = 1
 │   ├─ fib(3)                        dp[2] = dp[0] + dp[1] = 1
 │   │   ├─ fib(2) ← computed 3x!     dp[3] = dp[1] + dp[2] = 2
 │   │   └─ fib(1)                    dp[4] = dp[2] + dp[3] = 3
 │   └─ fib(2) ← again               dp[5] = dp[3] + dp[4] = 5
 └─ fib(3)     ← again
    ...                              Each subproblem solved exactly once!

The 3-Step Recipe

Every 1D DP problem follows these steps:

Step 1: Define State

What does dp[i] represent? This is the hardest and most important step.

  • "The number of ways to reach step i"
  • "The maximum amount we can rob from houses 0..i"
  • "The minimum coins needed to make amount i"

Step 2: Write Recurrence

How does dp[i] relate to previous states?

  • Climbing stairs: dp[i] = dp[i-1] + dp[i-2]
  • House robber: dp[i] = max(dp[i-1], dp[i-2] + nums[i])
  • Coin change: dp[i] = min(dp[i-c] + 1) for each coin c

Step 3: Set Base Cases

What are the trivially known values?

  • Climbing stairs: dp[0] = 1, dp[1] = 1
  • House robber: dp[0] = nums[0], dp[1] = max(nums[0], nums[1])
  • Coin change: dp[0] = 0 (zero coins for amount zero)

Top-Down vs Bottom-Up

Top-down (memoization): Start from the target, recurse down, cache results.

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

Bottom-up (tabulation): Fill a table from base cases up to the target.

def fib(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]

Bottom-up is generally preferred in interviews: no recursion overhead, easier to optimize space, and the iteration direction is explicit.

Five 1D DP Archetypes

1. Fibonacci-Style

State depends on a fixed number of previous states. Classic: climbing stairs, tiling problems. dp[i] = dp[i-1] + dp[i-2]

2. Take/Skip (Decision at Each Element)

For each element, choose to include it or skip it. Classic: house robber, paint houses. dp[i] = max(dp[i-1], dp[i-2] + value[i])

3. Knapsack (Optimizing Over Choices)

For each capacity/target value, try all items. Classic: coin change, subset sum. dp[j] = min(dp[j], dp[j - coin] + 1)

4. Subsequence

dp[i] depends on all dp[j] where j < i and some condition holds. Classic: LIS, longest divisible subset. dp[i] = max(dp[j] + 1) for all j < i where nums[j] < nums[i]

5. Subarray Tracking (Kadane-style)

Track a running property that can reset. Classic: max subarray sum, max product subarray. curMax = max(nums[i], curMax + nums[i])

Space Optimization

When dp[i] only depends on the last 1-2 values, replace the array with variables:

# Before: O(n) space
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
    dp[i] = dp[i-1] + dp[i-2]

# After: O(1) space
prev2, prev1 = 0, 1
for i in range(2, n + 1):
    curr = prev1 + prev2
    prev2, prev1 = prev1, curr

Common Mistakes

  1. Wrong base case — Off-by-one errors in dp[0] vs dp[1] are the #1 DP bug. Always verify your base cases against the problem's smallest inputs (n=0, n=1).
  2. Wrong iteration direction — Bottom-up must iterate so that dependencies are already computed. For knapsack-style problems, iterating in the wrong direction can use values from the current round instead of the previous round.
  3. Missing transitions — Forgetting a case in the recurrence (e.g., only considering "take" but not "skip"). Write out all choices explicitly before coding.
  4. Returning dp[n] vs dp[n-1] — If dp is 0-indexed and represents "answer for first i items", the answer is dp[n], not dp[n-1]. Match your indexing to your state definition.
  5. Space optimization bugs — When reducing to O(1) space, update variables in the wrong order and overwrite values you still need. Always update in the correct sequence and use temporary variables.

When to Use

The problem asks for **minimum/maximum** cost, value, or length to reach a target
You need to count the **number of ways** to do something
The problem involves **take/skip** choices at each element (rob or skip, buy or sell)
Keywords: minimum coins, number of ways, can you reach, longest/shortest
The brute-force solution has **exponential time** due to repeated subproblems
The problem has a natural 1D state: one index, one amount, or one position
You can define `dp[i]` as the answer for a prefix, suffix, or capacity `i`

Template

1# --- Bottom-Up DP Template ---
2def solve(n, ...):
3    # Step 1: Define state — what does dp[i] represent?
4    dp = [0] * (n + 1)
5
6    # Step 3: Base cases
7    dp[0] = base_value
8    # dp[1] = ...
9
10    # Step 2: Fill using recurrence
11    for i in range(1, n + 1):
12        # dp[i] = f(dp[i-1], dp[i-2], ...)
13        pass
14
15    return dp[n]
16
17# --- Space-Optimized Template ---
18def solve_optimized(n, ...):
19    # When dp[i] only depends on last 1-2 values
20    prev2 = base0
21    prev1 = base1
22    for i in range(2, n + 1):
23        curr = f(prev1, prev2)
24        prev2, prev1 = prev1, curr
25    return prev1
{ }

Syntax Reference

1# --- DP Array Initialization ---
2dp = [0] * (n + 1)                     # n+1 slots, all zero
3dp = [float('inf')] * (n + 1)          # For minimization problems
4dp = [False] * (n + 1)                 # For boolean DP (can reach?)
5dp[0] = base_value                     # Set base case
6
7# --- Bottom-Up Iteration ---
8for i in range(1, n + 1):              # Fill left to right
9    dp[i] = recurrence(dp[i-1], dp[i-2], ...)
10
11# --- Space-Optimized (2 variables) ---
12prev2, prev1 = base0, base1
13for i in range(2, n + 1):
14    curr = f(prev1, prev2)
15    prev2, prev1 = prev1, curr
16# Answer: prev1
17
18# --- Top-Down with Memoization ---
19from functools import lru_cache
20
21@lru_cache(maxsize=None)
22def solve(i):
23    if i <= base: return base_value
24    return recurrence(solve(i-1), solve(i-2), ...)
📋

Common Recipes

1# Recipe 1: Climbing Stairs (Fibonacci-style)
2def climb_stairs(n):
3    if n <= 2:
4        return n
5    prev2, prev1 = 1, 2
6    for i in range(3, n + 1):
7        curr = prev1 + prev2
8        prev2, prev1 = prev1, curr
9    return prev1
10
11# Recipe 2: House Robber (Take/Skip)
12def rob(nums):
13    if len(nums) == 1:
14        return nums[0]
15    prev2, prev1 = nums[0], max(nums[0], nums[1])
16    for i in range(2, len(nums)):
17        curr = max(prev1, prev2 + nums[i])
18        prev2, prev1 = prev1, curr
19    return prev1
20
21# Recipe 3: Coin Change (Unbounded Knapsack)
22def coin_change(coins, amount):
23    dp = [float('inf')] * (amount + 1)
24    dp[0] = 0
25    for coin in coins:
26        for j in range(coin, amount + 1):
27            dp[j] = min(dp[j], dp[j - coin] + 1)
28    return dp[amount] if dp[amount] != float('inf') else -1
29
30# Recipe 4: Longest Increasing Subsequence
31def length_of_lis(nums):
32    n = len(nums)
33    dp = [1] * n
34    for i in range(1, n):
35        for j in range(i):
36            if nums[j] < nums[i]:
37                dp[i] = max(dp[i], dp[j] + 1)
38    return max(dp)
O(n)

Complexity

ArchetypeTimeSpaceExample
Fibonacci-styleO(n)O(1)*Climbing Stairs, Tribonacci
Take/SkipO(n)O(1)*House Robber, Paint Houses
Knapsack (unbounded)O(n · k)O(n)Coin Change (k = coins)
Subsequence (O(n²))O(n²)O(n)LIS, Longest Divisible Subset
Subarray trackingO(n)O(1)Max Subarray, Max Product Subarray

Watch Out

  • ✗Wrong base case — Off-by-one errors in `dp[0]` vs `dp[1]` are the #1 DP bug. Always verify your base cases against the problem's smallest inputs (n=0, n=1).
  • ✗Wrong iteration direction — Bottom-up must iterate so that dependencies are already computed. For knapsack-style problems, iterating in the wrong direction can use values from the current round instead of the previous round.
  • ✗Missing transitions — Forgetting a case in the recurrence (e.g., only considering "take" but not "skip"). Write out all choices explicitly before coding.
  • ✗Returning dp[n] vs dp[n-1] — If dp is 0-indexed and represents "answer for first i items", the answer is `dp[n]`, not `dp[n-1]`. Match your indexing to your state definition.
  • ✗Space optimization bugs — When reducing to O(1) space, update variables in the wrong order and overwrite values you still need. Always update in the correct sequence and use temporary variables.
PRACTICE PROBLEMS
Previous
Backtracking
Next
Greedy