12.1 1D Linear & Knapsack Dynamic Programming

1. Start With a Real Problem: Why Does Plain Recursion Crash?

Imagine someone asks you on a whiteboard: "What is 1 + 1 + 1 + 1 + 1?" You count five 1s and say 5. Then they write + 1 at the end and ask: "Now what is the total?" Do you start counting from the very first 1 all over again? No! You already know the first five 1s add up to 5, so you just compute 5 + 1 = 6 in one step.

That is the entire secret of Dynamic Programming (DP):

Dynamic Programming = Recursion (trying all valid choices) + Remembering past answers in a notebook so you NEVER solve the exact same subproblem twice.

What Happens When You Forget to Write Answers Down (O(2^N))

In Climbing Stairs, you can climb 1 or 2 steps at a time. To reach step 5, you must come from either step 4 or step 3, so ways(5) = ways(4) + ways(3). Look at the recursion tree below if you write plain recursion return ways(n - 1) + ways(n - 2):

• For n = 5, fib(3) is computed 2 times and fib(2) is computed 3 times.
• For n = 50, plain recursion recomputes the exact same small steps over 20,000,000,000,000 (20 trillion) times (O(2^N)) and immediately hits Time Limit Exceeded (TLE)!
• Yet how many distinct questions exist between 0 and 50? Only 51 questions (ways(0) through ways(50))! Once we cache each answer the first time we compute it, 20 trillion steps collapse to 50 steps (O(N))!

2. How to Spot a DP Problem in a Product-Company Interview

In interviews at Google, Amazon, Meta, or Uber, nobody will tell you "Use Dynamic Programming." How do you know within 60 seconds whether a problem needs DP, Greedy, or Backtracking?

1. The Question Clue:
   • Backtracking asks you to list every actual combination ("Return all subsets / all valid arrangements"). Because the output itself has 2^N items, you must take O(2^N) time.
   • Dynamic Programming asks for a single optimal number or boolean:
     • "What is the minimum number of coins / jumps / edits?"
     • "What is the maximum profit / rob amount / subarray product?"
     • "How many distinct ways can you decode this string / reach the end?"
     • "Is it possible (True/False) to partition this array / segment this word?"
2. Why Greedy Fails and DP Wins (The Coin Change Test): Suppose you have coins [1, 3, 4] and need to make amount = 6 using the fewest coins:
   • Greedy grabs the biggest coin first (4), leaving 2, which forces 4 + 1 + 1 (3 coins).
   • Dynamic Programming doesn't guess! At amount = 6, it tries all 3 possible last coins (1, 3, and 4), looks up the exact pre-solved answer for the remainder (dp[5], dp[3], dp[2]), and discovers 3 + 3 (2 coins)!

Step Through the Visual Drawing Below

Click Next on the interactive stepper below to watch how a 1D DP table solves coins = [1, 3, 4], amount = 6 step by step without guessing:

3. The 4-Stage Product-Company DP Blueprint (How to Solve ANY DP Problem)

Never try to invent a bottom-up array out of thin air in an interview! Top candidates follow the exact same 4 stages on every problem. Let's walk through all 4 stages on House Robber ("Rob houses along a street to maximize cash, but you cannot rob two adjacent houses"):

Stage 1: Define the State & Choice Recurrence (Plain Recursion — O(2^N))

Stand at house i. What are your only two legal choices?

1. Skip house i: You get 0 from house i, and your best total from the first i houses is simply solve(i - 1).
2. Rob house i: You collect nums[i] cash, which bans you from robbing i - 1, so you add solve(i - 2).

• Recurrence Formula: solve(i) = max(solve(i - 1), nums[i] + solve(i - 2))

Stage 2: Top-Down Memoization (Add a memo Cache — O(N) Time, O(N) Space)

Take your exact Stage 1 recursive function and add 3 lines: if i in memo: return memo[i], and save memo[i] = ans before returning. In an interview, you already have an optimal O(N) time solution right here!

Stage 3: Bottom-Up Tabulation (Convert Recursion to a for Loop — O(N) Time, O(N) Space)

Replace recursive calls solve(i) with array lookups dp[i] and loop i from 0 to n - 1 so smaller indices are already filled before dp[i] reads them:

Stage 4: Space Optimization (O(N) Space → O(1) Space)

Look at dp[i] = max(dp[i - 1], nums[i] + dp[i - 2]). To compute dp[i], do we ever look at dp[i - 3] or dp[0]? No! We only ever read the last two values. So we replace the entire dp[] array with two variables: prev2 (dp[i - 2]) and prev1 (dp[i - 1])!

Compare All 4 Stages Side-by-Side (All 4 Languages)

# STAGE 1: Brute-Force Recursion -> O(2^N) Time (TLE!)
def rob_stage1(nums: list[int]) -> int:
  def dfs(i: int) -> int:
      if i < 0: return 0
      return max(dfs(i - 1), nums[i] + dfs(i - 2))
  return dfs(len(nums) - 1)

# STAGE 2: Top-Down Memoization (Recursion + Cache) -> O(N) Time, O(N) Space
def rob_stage2(nums: list[int]) -> int:
  memo = {}
  def dfs(i: int) -> int:
      if i < 0: return 0
      if i in memo: return memo[i]
      memo[i] = max(dfs(i - 1), nums[i] + dfs(i - 2))
      return memo[i]
  return dfs(len(nums) - 1)

# STAGE 3: Bottom-Up Tabulation (1D Array) -> O(N) Time, O(N) Space
def rob_stage3(nums: list[int]) -> int:
  n = len(nums)
  if n == 1: return nums[0]
  dp = [0] * n
  dp[0] = nums[0]
  dp[1] = max(nums[0], nums[1])
  for i in range(2, n):
      dp[i] = max(dp[i - 1], nums[i] + dp[i - 2])
  return dp[-1]

# STAGE 4: Space-Optimized Bottom-Up -> O(N) Time, O(1) Space!
def rob_stage4(nums: list[int]) -> int:
  prev2, prev1 = 0, 0
  for x in nums:
      prev2, prev1 = prev1, max(prev1, prev2 + x)
  return prev1

4. Deep Dive: The Knapsack Family (0/1 vs. Unbounded)

Half of all Medium/Hard 1D DP questions in product companies are secretly Knapsack problems in disguise ("You have a list of items/coins/numbers and a target capacity/sum").

There are only two flavors of Knapsack, and the only difference in code is whether the inner loop goes BACKWARD or FORWARD:

1. 0/1 Knapsack (Each item can be used AT MOST ONCE — e.g., Partition Equal Subset Sum, Target Sum):
   • Suppose x = 3 and we want to update dp[s] = dp[s] or dp[s - 3].
   • If you loop s forward from 3 to target: first dp[3] becomes True (using 3 once). Then when the loop reaches s = 6, it reads dp[6 - 3] = dp[3] (which is now True!) and sets dp[6] = True — accidentally using the single number 3 twice!
   • The Fix: Loop s BACKWARD from target down to x! That way dp[6] reads the old dp[3] from before x = 3 was used!
2. Unbounded Knapsack (Each item can be reused UNLIMITED TIMES — e.g., Coin Change):
   • Here we want to allow using coin 3 multiple times (3 + 3 = 6)!
   • So we loop a FORWARD from coin up to amount.

# 1. 0/1 Knapsack: Partition Equal Subset Sum (Use each number AT MOST ONCE -> BACKWARD loop!)
def can_partition(nums: list[int]) -> bool:
  total = sum(nums)
  if total % 2 == 1:
      return False
  target = total // 2
  dp = [False] * (target + 1)
  dp[0] = True  # Sum 0 is always achievable (pick nothing)
  for x in nums:
      for s in range(target, x - 1, -1):  # BACKWARD so x is used once!
          dp[s] = dp[s] or dp[s - x]
  return dp[target]

# 2. Unbounded Knapsack: Coin Change (Reuse coins UNLIMITED times -> FORWARD loop!)
def coin_change(coins: list[int], amount: int) -> int:
  dp = [amount + 1] * (amount + 1)
  dp[0] = 0
  for c in coins:
      for a in range(c, amount + 1):      # FORWARD so c can build on itself!
          dp[a] = min(dp[a], 1 + dp[a - c])
  return dp[amount] if dp[amount] <= amount else -1

5. Core Interview Patterns & Common Traps

# 0/1 Knapsack (use each x at most once -> BACKWARD loop):
for x in nums:
  for s in range(target, x - 1, -1):
      dp[s] = dp[s] or dp[s - x]

# Unbounded Knapsack (reuse c unlimited times -> FORWARD loop):
for c in coins:
  for a in range(c, amount + 1):
      dp[a] = min(dp[a], 1 + dp[a - c])

6. Practice On Your Own (Curated Submodule Problems)