Dynamic Programming: 1D

Updated Nov 19, 2026 · 4 min read
On this page

    Dynamic programming is recursion that remembers. If the brute-force recursion solves the same smaller problem many times, store each answer the first time and reuse it. In one-dimensional DP, a smaller problem is described by one number: a prefix of the array, an amount of money, a position in a string. You fill a list dp where dp[i] is the answer for that smaller problem.

    The code is always short. The work is in four decisions, made in this order:

    1. State: what does dp[i] mean, in one sentence?
    2. Recurrence: how does dp[i] come from smaller states?
    3. Base case: which states are known without thinking?
    4. Order: fill states so everything dp[i] needs is ready first.

    When to recognise it

    • "Minimum / maximum / number of ways" to reach something: fewest coins, most money robbed, ways to climb stairs, ways to decode.
    • "Can it be done?" where a choice at each step affects later steps: word break, jump game variants.
    • A brute force that branches ("take it or skip it", "use this coin or not") and repeats work.
    • Longest increasing / alternating subsequence: the state is "best ending at index i".
    • Contrast with Greedy: if one local rule always works, you don't need DP. If you can build a counterexample to the greedy rule (coins [1, 3, 4], amount 6), you need DP.

    Example: house robber

    You can't rob two neighbouring houses. State: dp[i] = the most money from the first i houses. Recurrence: for house i, either skip it (dp[i − 1]) or rob it and skip its neighbour (dp[i − 2] + houses[i − 1]).

    Houses [2, 7, 9, 3, 1] above a dp row [0, 2, 7, 11, 11, 12]. dp[1] and dp[2] are highlighted as inputs to dp[3]: max(7, 2 + 9) = 11.
    Houses [2, 7, 9, 3, 1] above a dp row [0, 2, 7, 11, 11, 12]. dp[1] and dp[2] are highlighted as inputs to dp[3]: max(7, 2 + 9) = 11.

    Since dp[i] reads only the two states before it, two variables replace the list:

    def rob(houses):
        """dp[i] = best using houses[:i]. Only the last two states matter, so keep two variables."""
        prev2 = prev1 = 0                 # dp[i-2], dp[i-1]
        for x in houses:
            prev2, prev1 = prev1, max(prev1, prev2 + x)   # skip house i, or take it
        return prev1

    Time O(n), space O(1).

    Template: bottom-up table

    def coin_change(coins, amount):
        """Bottom-up: dp[a] = fewest coins to make a. Fill small amounts first."""
        INF = float('inf')
        dp = [0] + [INF] * amount
        for a in range(1, amount + 1):
            for c in coins:
                if c <= a and dp[a - c] + 1 < dp[a]:
                    dp[a] = dp[a - c] + 1
        return dp[amount] if dp[amount] != INF else -1
    Coin change with coins [1, 2, 5]: a row of dp values for amounts 0 to 11 (0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3). dp[11] = 1 + min(dp[10], dp[9], dp[6]) = 3.
    Coin change with coins [1, 2, 5]: a row of dp values for amounts 0 to 11 (0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3). dp[11] = 1 + min(dp[10], dp[9], dp[6]) = 3.

    Time O(amount × coins), space O(amount).

    Top-down is the same thing

    If the recurrence is clearer as recursion, write it that way and add a cache. In an interview this is a good first version; convert to a table if asked about recursion depth or speed.

    from functools import lru_cache
    
    def coin_change_memo(coins, amount):
        """Top-down: same recurrence written as recursion + cache. Good first draft in an interview."""
        @lru_cache(maxsize=None)
        def best(a):
            if a == 0:
                return 0
            if a < 0:
                return float('inf')
            return 1 + min(best(a - c) for c in coins)
        r = best(amount)
        return -1 if r == float('inf') else r

    Two more shapes

    Look back over every split. dp[i] is true if some earlier dp[j] is true and the piece s[j:i] is a word:

    def word_break(s, words):
        """dp[i] = can s[:i] be split? Look back at every possible last word."""
        words = set(words)
        dp = [True] + [False] * len(s)
        for i in range(1, len(s) + 1):
            dp[i] = any(dp[j] and s[j:i] in words for j in range(i))
        return dp[len(s)]

    Best ending here. For the longest increasing subsequence, the O(n²) DP is dp[i] = 1 + max(dp[j] for j < i if nums[j] < nums[i]). The faster version keeps, for each length, the smallest possible last value, and uses binary search:

    import bisect
    
    def lis_length(nums):
        """O(n log n): tails[k] = smallest tail of an increasing run of length k + 1."""
        tails = []
        for x in nums:
            i = bisect.bisect_left(tails, x)
            if i == len(tails):
                tails.append(x)
            else:
                tails[i] = x
        return len(tails)

    Common bugs

    • A fuzzy state. If you can't say what dp[i] means in one sentence, the recurrence will be wrong. Write the sentence down.
    • Off-by-one between dp and the input: with dp[i] meaning "first i items", item i is houses[i − 1].
    • Wrong base case: dp[0] = 0 for "fewest coins for amount 0", but 1 for "number of ways to make 0".
    • Unreachable states: start them at infinity (or −1) and check before using them, as coin_change does.
    • Counting order matters. For "number of combinations" (coin change II), loop over coins outside and amounts inside; swapping the loops counts permutations instead.

    Say this in the interview

    • "Let dp[i] be the best I can do with the first i houses. For house i I either skip it, giving dp[i − 1], or take it, giving dp[i − 2] plus its value."
    • "Each state is computed once from a constant number of earlier states, so it's O(n) time, and since I only look back two steps I can keep two variables."

    Problems for this pattern

    1. Climbing Stairs: dp[i] = dp[i − 1] + dp[i − 2].
    2. Maximum Subarray: best sum ending here.
    3. House Robber: skip or take.
    4. Coin Change: the table template.
    5. Decode Ways: one-digit and two-digit steps.
    6. Word Break: look back over every split.
    7. Longest Increasing Subsequence: best ending here, then the binary-search speed-up.
    8. Maximum Product Subarray: track both the max and the min ending here.

    Related

    DP 2D · Backtracking (the recursion before the cache) · Greedy · Binary Search