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

By /
⏱ 4 min read

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
  • LinkedIn Interview Guide
  • Atlassian Interview Guide
  • Uber Interview Guide
  • Apple Interview Guide
  • Meta Interview Guide

    • 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
    Scroll to Top