# 1D Dynamic Programming Interview Patterns: House Robber, LIS, Coin Change, Word Break

Source: https://www.techinterview.org/post/3233463177/dynamic-programming-1d-interview-patterns/
Updated: 2026-04-17 · techinterview.org

## 1D Dynamic Programming Interview Patterns

1D DP problems have a state space that reduces to a single index or value. The recurrence depends only on a constant number of previous states, enabling O(N) time and O(1) space solutions after recognizing the pattern.

- [Coinbase Interview Guide](https://techinterview.org/coinbase-software-engineer-interview/)

- [LinkedIn Interview Guide](https://techinterview.org/linkedin-software-engineer-interview/)

- [Atlassian Interview Guide](https://techinterview.org/atlassian-software-engineer-interview/)

- [Uber Interview Guide](https://techinterview.org/uber-software-engineer-interview/)

- [Apple Interview Guide](https://techinterview.org/apple-software-engineer-interview/)

- [Meta Interview Guide](https://techinterview.org/meta-software-engineer-interview/)

## Pattern 1: Linear Sequence (House Robber)


```
def rob(nums):
    prev2, prev1 = 0, 0
    for n in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + n)
    return prev1
# dp[i] = max(dp[i-1], dp[i-2] + nums[i])
# "take or skip" recurrence
```

Applications: House Robber I/II, Maximum Alternating Subsequence, any "pick non-adjacent elements" problem. Space optimization: only need prev two values → O(1) space.

## Pattern 2: Climbing Stairs / Fibonacci-style


```
def climb_stairs(n):
    a, b = 1, 1
    for _ in range(2, n+1):
        a, b = b, a + b
    return b
# dp[i] = dp[i-1] + dp[i-2]
```

Applications: Climbing Stairs, Decode Ways (count decodings of digit string), Min Cost Climbing Stairs. Decode Ways adds validity check: single digit (not 0) or two digits (10–26) must be valid.

## Pattern 3: Unbounded Knapsack (Coin Change)


```
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
```

Unbounded: each item (coin) can be used multiple times. Iterate amounts outer, coins inner. 0/1 Knapsack (each item once): iterate items outer, amounts inner (backward to prevent reuse).

## Pattern 4: Longest Increasing Subsequence (LIS)


```
# O(N^2) DP
def lis_n2(nums):
    dp = [1] * len(nums)
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

# O(N log N) patience sorting
def lis_nlogn(nums):
    tails = []
    for n in nums:
        lo, hi = 0, len(tails)
        while lo < hi:
            mid = (lo+hi)//2
            if tails[mid] < n: lo = mid+1
            else: hi = mid
        if lo == len(tails): tails.append(n)
        else: tails[lo] = n
    return len(tails)
```

The patience sorting approach maintains a list of "tail" values of increasing subsequences. Binary search finds where to place each number. Length of tails = LIS length.

## Pattern 5: Palindromic Subsequence


```
def longest_palindromic_subseq(s):
    n = len(s)
    dp = [[0]*n for _ in range(n)]
    for i in range(n): dp[i][i] = 1
    for length in range(2, n+1):
        for i in range(n-length+1):
            j = i + length - 1
            if s[i] == s[j]:
                dp[i][j] = dp[i+1][j-1] + 2
            else:
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])
    return dp[0][n-1]
```


## Pattern 6: Word Break


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


## Recognizing 1D DP Problems

  - "Maximum/minimum over a sequence" + optimal substructure → DP

  - Counting distinct ways → DP (sum over valid previous states)

  - Decision at each element: take or skip → House Robber pattern

  - String segmentation or matching → Word Break / Decode Ways