Linear DP (1D): Master One-Dimensional Dynamic Programming

What is Linear DP?

Linear DP (One-Dimensional Dynamic Programming) is the most fundamental DP pattern where the state depends on previous elements in a single sequence. The DP table is a 1D array where dp[i] represents the optimal solution for a subproblem involving elements from index 0 to i.

Core Characteristics

1. Single Dimension State: dp[i] represents some optimal value at position i
2. Sequential Dependency: Each state depends on one or more previous states
3. Linear Iteration: We iterate through the array once (or a constant number of times)
4. Common Time Complexity: $O(n)$ to $O(n^2)$

Common Linear DP Patterns

Pattern	State Definition	Transition	Example
Take or Skip	dp[i] = optimal considering 0..i	dp[i] = max(dp[i-1], dp[i-2] + val[i])	House Robber
Extend or Restart	dp[i] = optimal ending at i	dp[i] = max(dp[i-1] + val[i], val[i])	Max Subarray
Counting	dp[i] = ways to reach state i	dp[i] = dp[i-1] + dp[i-2]	Climbing Stairs
Bounded Search	dp[i] = optimal for prefix i	dp[i] = min(dp[j] + cost) for valid j	Word Break

---

The “Take or Skip” Pattern

This is one of the most common Linear DP patterns. At each position, you decide whether to “take” the current element (which affects what you can take previously) or “skip” it.

Visual Intuition

House Robber: Can't rob adjacent houses

Houses:    [2]  [7]  [9]  [3]  [1]
Index:      0    1    2    3    4

At each house, you have 2 choices:
  - ROB it: Add its value + best from 2 houses back
  - SKIP it: Take best from previous house

dp[0] = 2        (rob house 0)
dp[1] = max(7, 2) = 7   (skip 0, rob 1 OR rob 0, skip 1)
dp[2] = max(7, 2+9) = 11 (skip 2 OR rob 0 and 2)
dp[3] = max(11, 7+3) = 11 (skip 3 OR rob 1 and 3)
dp[4] = max(11, 11+1) = 12 (skip 4 OR rob 0,2,4)

---

Interactive Visualization: House Robber

Loading visualization...

---

Problem 1: House Robber (LC 198)

Problem: Rob houses along a street. Can’t rob two adjacent houses. Maximize total money.

State Definition: dp[i] = maximum money robbing houses 0 to i

Transition:

dp[i] = max(
    dp[i-1],           // Skip current house
    dp[i-2] + nums[i]  // Rob current house
)

Key Insight: This is a classic “take or skip” pattern with constraint (can’t take adjacent).

JavaPythonJavaScript

Loading...

Space Optimization

Since dp[i] only depends on dp[i-1] and dp[i-2], we can reduce space from $O(n)$ to $O(1)$:

prev2 ← prev1 ← current

---

The “Extend or Restart” Pattern

At each position, decide whether to extend the previous optimal solution or start fresh from the current position.

Visual Intuition: Kadane’s Algorithm

Maximum Subarray: Find contiguous subarray with max sum

Array:  [-2]  [1]  [-3]  [4]  [-1]  [2]  [1]  [-5]  [4]
Index:    0    1     2    3     4    5    6     7    8

At each position:
  - EXTEND: Add current to previous best ending here
  - RESTART: Start new subarray from current element

dp[0] = -2  (only choice)
dp[1] = max(1, -2+1) = 1      (restart is better!)
dp[2] = max(-3, 1-3) = -2     (extend is better)
dp[3] = max(4, -2+4) = 4      (restart is better!)
dp[4] = max(-1, 4-1) = 3      (extend)
dp[5] = max(2, 3+2) = 5       (extend)
dp[6] = max(1, 5+1) = 6       (extend)  ← Global maximum!

---

Interactive Visualization: Maximum Subarray

Loading visualization...

---

Problem 2: Maximum Subarray (LC 53)

Problem: Find the contiguous subarray with the largest sum.

State Definition: dp[i] = maximum subarray sum ending at index i

Transition:

dp[i] = max(
    nums[i],              // Start new subarray
    dp[i-1] + nums[i]     // Extend previous subarray
)

Key Insight: If dp[i-1] is negative, starting fresh is always better!

JavaPythonJavaScript

Loading...

Why This Works

The key insight of Kadane’s algorithm:

• If the best subarray ending at i-1 is positive, extending it can only help
• If it’s negative, we’re better off starting fresh

---

The “Unbounded Knapsack” Pattern

When you can use items multiple times to reach a target, the state represents the target value, and we iterate through all items at each step.

Visual Intuition: Coin Change

Coins: [1, 2, 5], Amount: 11

dp[i] = minimum coins to make amount i
dp[0] = 0 (base case)

For each amount from 1 to 11:
  Try each coin and take minimum

Amount 1: coin 1 → dp[0]+1=1          → dp[1]=1
Amount 2: coin 1 → dp[1]+1=2
          coin 2 → dp[0]+1=1          → dp[2]=1
Amount 5: coin 1 → dp[4]+1=3
          coin 2 → dp[3]+1=3
          coin 5 → dp[0]+1=1          → dp[5]=1
Amount 11: coin 1 → dp[10]+1=4
           coin 2 → dp[9]+1=4
           coin 5 → dp[6]+1=3         → dp[11]=3

---

Interactive Visualization: Coin Change

Loading visualization...

---

Problem 3: Coin Change (LC 322)

Problem: Find minimum number of coins to make the amount. Unlimited coins available.

State Definition: dp[i] = minimum coins to make amount i

Transition:

dp[i] = min(dp[i - coin] + 1) for each coin where coin <= i

JavaPythonJavaScript

Loading...

Related Problems

• LC 518: Coin Change II - Count combinations
• LC 279: Perfect Squares - Same pattern with squares

---

Problem 4: Decode Ways (LC 91)

Problem: Count ways to decode a digit string (1→A, 2→B, …, 26→Z).

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

Transition:

dp[i] = 0
if s[i-1] is valid single digit (1-9):  dp[i] += dp[i-1]
if s[i-2..i-1] is valid two digits (10-26): dp[i] += dp[i-2]

Key Insight: Similar to Climbing Stairs, but with conditional transitions.

JavaPythonJavaScript

Loading...

Edge Cases

• Leading zeros: “0” or “00” → Invalid
• Zero in middle: “10” valid, “01” invalid
• Numbers > 26: “27” can only decode as “2”,“7”

---

Problem 5: Longest Increasing Subsequence (LC 300)

Problem: Find length of longest strictly increasing subsequence.

DP Approach - $O(n^2)$

State Definition: dp[i] = length of LIS ending at index i

Transition:

dp[i] = max(dp[j] + 1) for all j < i where nums[j] < nums[i]

This approach is intuitive but requires checking all previous elements for each position, resulting in $O(n^2)$ time.

JavaPythonJavaScript

Loading...

Binary Search Approach - $O(n \log n)$

Key Insight: Maintain a tails array where tails[i] represents the smallest tail element among all increasing subsequences of length i+1.

Think of it as maintaining a “candidate pool” - for each possible LIS length, we only keep the “most promising” one (smallest ending element, because smaller endings have more room to extend).

Why does this work?

• Greedy strategy: A smaller ending element gives more chances to extend the subsequence
• Key property: The tails array is always strictly increasing
  • Proof: If tails[i] >= tails[i+1], that means a longer LIS has a smaller or equal ending than a shorter one, which is impossible

Because tails is sorted, we can use binary search to find the right position in $O(\log n)$ time.

Algorithm:

1. For each new element num:
   • Binary search to find the first position where tails[pos] >= num
   • If found: replace tails[pos] with num (optimize this length’s smallest ending)
   • If not found (num is largest): append num to extend LIS
2. Final answer = len(tails)

Step-by-step Example:

nums = [10, 9, 2, 5, 3, 7, 101, 18]

Process 10:  tails = [10]
  → First element, length-1 LIS ends with 10

Process 9:   tails = [9]
  → 9 < 10, replace. Length-1 LIS now ends with 9 (better than 10)

Process 2:   tails = [2]
  → 2 < 9, replace. Length-1 LIS now ends with 2 (best so far)

Process 5:   tails = [2, 5]
  → 5 > 2, extend! Now we have length-2 LIS ending with 5

Process 3:   tails = [2, 3]
  → 3 > 2 but 3 < 5, replace position 1
  → Length-2 LIS [2,3] is better than [2,5] (smaller ending)

Process 7:   tails = [2, 3, 7]
  → 7 > 3, extend! Length-3 LIS ending with 7

Process 101: tails = [2, 3, 7, 101]
  → 101 > 7, extend! Length-4 LIS ending with 101

Process 18:  tails = [2, 3, 7, 18]
  → 18 > 7 but 18 < 101, replace position 3
  → Length-4 LIS ending with 18 is better (smaller ending)

Final: len(tails) = 4, so LIS length is 4

Important Note: The tails array is NOT the actual LIS! It only tells us the length. In the example above, tails = [2, 3, 7, 18] but an actual LIS could be [2, 5, 7, 101] or [2, 3, 7, 18].

Complexity Comparison:

Approach	Time	Space	When to Use
DP	$O(n^2)$	$O(n)$	n ≤ 2500, need to reconstruct sequence
Binary Search	$O(n \log n)$	$O(n)$	n ≤ $10^5$, only need length

JavaPythonJavaScript

Loading...

---

Problem 6: Word Break (LC 139)

Problem: Can the string be segmented into dictionary words?

State Definition: dp[i] = true if s[0..i-1] can be segmented

Transition:

dp[i] = true if there exists j < i such that:
    dp[j] is true AND s[j..i-1] is in dictionary

JavaPythonJavaScript

Loading...

---

Space Optimization Techniques

Most Linear DP can be optimized from $O(n)$ to $O(1)$ space:

When dp[i] depends on dp[i-1] and dp[i-2]

// Before: O(n) space
int[] dp = new int[n];
dp[0] = ...; dp[1] = ...;
for (int i = 2; i < n; i++) {
    dp[i] = f(dp[i-1], dp[i-2]);
}
return dp[n-1];

// After: O(1) space
int prev2 = ..., prev1 = ...;
for (int i = 2; i < n; i++) {
    int curr = f(prev1, prev2);
    prev2 = prev1;
    prev1 = curr;
}
return prev1;

When only dp[i-1] needed

// Just use a single variable!
int prev = base_value;
for (int i = 1; i < n; i++) {
    prev = f(prev, nums[i]);
}
return prev;

---

Common Patterns Summary

Problem Type	State	Transition	Time	Space
House Robber	max money 0..i	max(skip, take)	O(n)	O(1)
Max Subarray	max sum ending at i	max(extend, restart)	O(n)	O(1)
Climbing Stairs	ways to step i	dp[i-1] + dp[i-2]	O(n)	O(1)
Coin Change	min coins for amount	min(dp[i-coin]+1)	O(n*m)	O(n)
Decode Ways	ways to decode 0..i	conditional sum	O(n)	O(1)
Word Break	can segment 0..i	OR of valid splits	O(n²*m)	O(n)
LIS (DP)	LIS ending at i	max(dp[j]+1) if valid	O(n²)	O(n)
LIS (Binary Search)	smallest tail for length	binary search + replace	O(n log n)	O(n)

---

Interview Tips

How to Identify Linear DP

1. “Maximum/Minimum of…” with constraints → Take or Skip
2. “Count the number of ways…” → Addition of subproblems
3. “Is it possible…” → Boolean DP with OR
4. “Contiguous subarray” → Extend or Restart pattern

Common Mistakes

1. Forgetting base cases: Always handle n=0, n=1
2. Wrong iteration direction: Make sure dependencies are computed first
3. Off-by-one errors: Be clear if dp[i] means “first i” or “ending at i”
4. Not considering negative numbers: Affects restart decisions

Optimization Questions Interviewers Ask

1. “Can you optimize the space?” → Rolling array or variables
2. “Can you do better than O(n²)?” → Binary search (like LIS)
3. “What if the array is very large?” → Consider streaming approach

---

Practice Problems

Easy

• LC 70: Climbing Stairs
• LC 746: Min Cost Climbing Stairs

Medium

• LC 198: House Robber
• LC 213: House Robber II (circular)
• LC 53: Maximum Subarray
• LC 322: Coin Change
• LC 91: Decode Ways
• LC 300: Longest Increasing Subsequence
• LC 139: Word Break
• LC 152: Maximum Product Subarray

Hard

• LC 140: Word Break II
• LC 188: Best Time to Buy and Sell Stock IV

---

Summary

Linear DP Key Takeaways:

1. State is 1D: dp[i] represents optimal value at/until position i

2. Three main patterns:

   • Take or Skip: dp[i] = max(dp[i-1], dp[i-2] + val[i])
   • Extend or Restart: dp[i] = max(dp[i-1] + val[i], val[i])
   • Bounded Search: dp[i] = optimal(dp[j] + cost) for valid j

3. Space optimization: Most 1D DP can use O(1) space with rolling variables

4. Time complexity: Usually O(n) to O(n²), can sometimes optimize to O(n log n)

Master these patterns and you’ll handle 80% of Linear DP problems in interviews!