Dynamic Programming: 1D

What is dynamic programming?

DP solves problems that have two properties:

1. Optimal substructure — the optimal solution to the problem contains optimal solutions to subproblems.
2. Overlapping subproblems — the same subproblems are solved multiple times during naive recursion.

Contrast with divide-and-conquer: Merge sort splits an array into halves and merges results — the subproblems never overlap (left half and right half are disjoint). DP subproblems overlap, so we cache results to avoid recomputation.

Identifying DP problems

Ask these questions when you see a problem:

• “How many ways can you…?” → count DP
• “What is the minimum/maximum…?” → optimization DP
• “Is it possible to…?” → feasibility DP

If the answer is yes to any of those, and the brute force is exponential (try all combinations/sequences), DP likely applies.

Decision framework:

Can I define a state dp[i] where i represents a position, capacity, or prefix?
  └─ Does dp[i] depend only on dp[j] where j < i (or some bounded set)?
       └─ If yes → 1D DP. Define recurrence, base case, answer.

The DP template

Before writing any code, answer four questions:

1. State: What does dp[i] represent?
2. Recurrence: How does dp[i] depend on previous states?
3. Base case: What are the smallest valid values?
4. Answer: Is it dp[n], dp[n-1], or max(dp)?

Getting the state definition right is 80% of the problem.

Top-down: memoization

Recursive solution + a cache to avoid recomputing subproblems.

// Fibonacci with memoization
function fib(n: number, memo = new Map<number, number>()): number {
  if (n <= 1) return n
  if (memo.has(n)) return memo.get(n)!
  const result = fib(n - 1, memo) + fib(n - 2, memo)
  memo.set(n, result)
  return result
}

Time: O(n) — each subproblem computed once.
Space: O(n) — memo table + O(n) call stack.

Top-down is often easier to write because the structure mirrors the natural recursive definition. Start here when the recurrence isn’t obvious.

Bottom-up: tabulation

Iteratively fill a table from base cases up to the answer. No recursion, no stack overhead.

// Fibonacci bottom-up
function fibBottomUp(n: number): number {
  if (n <= 1) return n
  const dp = new Array(n + 1).fill(0)
  dp[0] = 0; dp[1] = 1
  for (let i = 2; i <= n; i++) dp[i] = dp[i-1] + dp[i-2]
  return dp[n]
}

Bottom-up is preferred in interviews — it’s easier to analyze space complexity and spot optimizations.

Space optimization: rolling variables

When dp[i] only depends on the previous 1 or 2 states, discard the full array:

// Fibonacci: O(1) space
function fibOptimal(n: number): number {
  if (n <= 1) return n
  let prev2 = 0, prev1 = 1
  for (let i = 2; i <= n; i++) {
    const curr = prev1 + prev2
    prev2 = prev1
    prev1 = curr
  }
  return prev1
}

This pattern applies to Climbing Stairs, House Robber, and many others.

Pattern 1: Linear DP

Climbing Stairs (LC 70)

State: dp[i] = number of distinct ways to reach step i.
Recurrence: dp[i] = dp[i-1] + dp[i-2] (came from step i-1 or i-2).
Base case: dp[1] = 1, dp[2] = 2.

function climbStairs(n: number): number {
  if (n <= 2) return n
  let prev2 = 1, prev1 = 2
  for (let i = 3; i <= n; i++) {
    const curr = prev1 + prev2
    prev2 = prev1
    prev1 = curr
  }
  return prev1
}

Structurally identical to Fibonacci. O(n) time, O(1) space.

House Robber (LC 198)

You cannot rob two adjacent houses. Maximize total stolen.

State: dp[i] = max money robbing from houses 0..i.
Recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i]) — either skip house i, or rob it and add to best result two houses back.
Base case: dp[0] = nums[0], dp[1] = max(nums[0], nums[1]).

function rob(nums: number[]): number {
  if (nums.length === 1) return nums[0]
  let prev2 = nums[0]
  let prev1 = Math.max(nums[0], nums[1])

  for (let i = 2; i < nums.length; i++) {
    const curr = Math.max(prev1, prev2 + nums[i])
    prev2 = prev1
    prev1 = curr
  }
  return prev1
}

House Robber II (LC 213): Houses in a circle. Run House Robber twice — once on nums[0..n-2], once on nums[1..n-1], take the max.

Pattern 2: Subsequence DP

Longest Increasing Subsequence — LIS (LC 300)

State: dp[i] = length of the LIS ending at index i.
Recurrence: dp[i] = max(dp[j] + 1) for all j < i where nums[j] < nums[i].
Base case: dp[i] = 1 (each element is a subsequence of length 1).

function lengthOfLIS(nums: number[]): number {
  const n = nums.length
  const dp = new Array(n).fill(1)

  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) {
        dp[i] = Math.max(dp[i], dp[j] + 1)
      }
    }
  }
  return Math.max(...dp)
}
// Time: O(n²), Space: O(n)

O(n log n) with patience sorting:

Maintain a tails array where tails[i] is the smallest tail element of all LIS of length i+1. Binary search to find where to place each element.

function lengthOfLISOptimal(nums: number[]): number {
  const tails: number[] = []

  for (const num of nums) {
    let lo = 0, hi = tails.length
    while (lo < hi) {
      const mid = (lo + hi) >> 1
      if (tails[mid] < num) lo = mid + 1
      else hi = mid
    }
    tails[lo] = num   // extend or replace
  }
  return tails.length
}
// Time: O(n log n), Space: O(n)

Pattern 3: Partition / knapsack DP

Coin Change (LC 322)

Minimum number of coins to make amount. Unlimited supply of each coin.

State: dp[i] = minimum coins to make amount i.
Recurrence: dp[i] = min(dp[i - coin] + 1) for each coin ≤ i.
Base case: dp[0] = 0, all others = Infinity.

function coinChange(coins: number[], amount: number): number {
  const dp = new Array(amount + 1).fill(Infinity)
  dp[0] = 0

  for (let i = 1; i <= amount; i++) {
    for (const coin of coins) {
      if (coin <= i && dp[i - coin] !== Infinity) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1)
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount]
}
// Time: O(amount × coins.length), Space: O(amount)

Coin Change 2 (LC 518) — count combinations

How many distinct combinations of coins sum to amount?

Key difference: iterate coins in outer loop to avoid counting permutations as different combinations.

function change(amount: number, coins: number[]): number {
  const dp = new Array(amount + 1).fill(0)
  dp[0] = 1                                // one way to make 0: use no coins

  for (const coin of coins) {              // outer loop over coins (not amount)
    for (let i = coin; i <= amount; i++) {
      dp[i] += dp[i - coin]
    }
  }
  return dp[amount]
}
// Time: O(amount × coins.length), Space: O(amount)

If you swap the loops (amount outer, coins inner), you count permutations — [1,2] and [2,1] are counted as different. Always process coins in outer loop for combination counting.

Pattern 4: String DP

Word Break (LC 139)

Can string s be segmented into words from wordDict?

State: dp[i] = true if s[0..i-1] can be segmented.
Recurrence: dp[i] = true if any dp[j] is true and s[j..i-1] is in the dictionary, for some j < i.
Base case: dp[0] = true (empty string is always valid).

function wordBreak(s: string, wordDict: string[]): boolean {
  const wordSet = new Set(wordDict)
  const dp = new Array(s.length + 1).fill(false)
  dp[0] = true

  for (let i = 1; i <= s.length; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && wordSet.has(s.slice(j, i))) {
        dp[i] = true
        break
      }
    }
  }
  return dp[s.length]
}
// Time: O(n² × m) where m = avg word length for slice/lookup, Space: O(n)

Pattern 5: State machine DP

Some problems have discrete states with transitions between them.

Best Time to Buy and Sell Stock with Cooldown (LC 309)

Three states at each day:

• held — currently holding a stock
• sold — just sold (must rest next day)
• rest — not holding, not just sold (can buy)

function maxProfit(prices: number[]): number {
  let held = -Infinity  // can't be holding stock at day 0 with no purchase
  let sold = 0          // profit from just selling
  let rest = 0          // profit from resting

  for (const price of prices) {
    const prevHeld = held, prevSold = sold, prevRest = rest
    held = Math.max(prevHeld, prevRest - price)  // keep holding OR buy today
    sold = prevHeld + price                       // sell today (was holding)
    rest = Math.max(prevRest, prevSold)           // rest today (was resting or just sold)
  }
  return Math.max(sold, rest)
}
// Time: O(n), Space: O(1)

State machine DP elegantly handles complex trading rules. The same framework applies to LC 188 (at most k transactions) and LC 123 (at most 2 transactions).

Pattern 6: Interval / token DP

Decode Ways (LC 91)

A string of digits can be decoded like a phone keypad (1-26 → A-Z). Count the ways.

State: dp[i] = number of ways to decode s[0..i-1].
Recurrence:

• Single digit s[i-1]: if it’s not ‘0’, add dp[i-1].
• Two digits s[i-2..i-1]: if it forms 10-26, add dp[i-2].

function numDecodings(s: string): number {
  const n = s.length
  const dp = new Array(n + 1).fill(0)
  dp[0] = 1                               // empty string: 1 way
  dp[1] = s[0] === '0' ? 0 : 1           // single digit

  for (let i = 2; i <= n; i++) {
    const oneDigit = parseInt(s[i-1])
    const twoDigits = parseInt(s.slice(i-2, i))

    if (oneDigit >= 1) dp[i] += dp[i-1]
    if (twoDigits >= 10 && twoDigits <= 26) dp[i] += dp[i-2]
  }
  return dp[n]
}
// Time: O(n), Space: O(n) — optimize to O(1) with rolling variables

Complexity reference

n = amount or string length, k = number of coins/words.

Common mistakes

1. Wrong state definition — if dp[i] is ambiguous (does it include index i or exclude it?), the recurrence breaks. Write the definition in a comment before coding.
2. Off-by-one in base cases — dp[0] often represents an empty prefix (0 items, 0 amount). Forgetting dp[0] = 1 in combination counting is a classic error.
3. Swapping loops in combination vs permutation problems — Coin Change 2 must iterate coins first to get combinations. Swapping gives permutation count.
4. Returning dp[n] vs max(dp) — for problems where the answer doesn’t have to include the last element (LIS, max subarray), the answer is the max over all dp values, not just the last one.
5. Not initializing with Infinity — for minimization problems, start with Infinity so the min operation works correctly. Starting with 0 gives wrong results.