1D Dynamic Programming

Shape of the problems

The input is a single sequence (array, string, or a number line up to n), and dp[i] summarizes the first i elements or the subsequence ending at i. Transitions look back a constant number of steps (O(n) total) or at all earlier indices (O(n²)).

Family 1: Take or skip (House Robber)

def rob(nums):
    prev2 = prev1 = 0              # best up to i-2, best up to i-1
    for x in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + x)
    return prev1

int rob(vector<int>& nums) {
    int prev2 = 0, prev1 = 0;
    for (int x : nums) {
        int cur = max(prev1, prev2 + x);
        prev2 = prev1; prev1 = cur;
    }
    return prev1;
}

Transformations to House Robber:

• Circular street: run it twice — without the first house and without the last.
• Delete and Earn: taking value v forbids v−1 and v+1 → sum points per value, then rob over the value line.
• Tree-shaped street: tree DP.

Family 2: Counting ways to decode / partition

dp[i] = number of ways to handle the prefix of length i. Look back one and two characters.

def num_decodings(s):
    n = len(s)
    dp = [0] * (n + 1)
    dp[0] = 1                                   # empty prefix: one way
    for i in range(1, n + 1):
        if s[i - 1] != "0":
            dp[i] += dp[i - 1]                  # single digit
        if i >= 2 and 10 <= int(s[i - 2:i]) <= 26:
            dp[i] += dp[i - 2]                  # two digits
    return dp[n]

Word break: look back at every possible last word

def word_break(s, word_dict):
    words = set(word_dict)
    max_len = max(map(len, words), default=0)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    for i in range(1, n + 1):
        for j in range(max(0, i - max_len), i):
            if dp[j] and s[j:i] in words:
                dp[i] = True
                break
    return dp[n]

bool wordBreak(string s, vector<string>& wordDict) {
    unordered_set<string> words(wordDict.begin(), wordDict.end());
    int n = s.size(), maxLen = 0;
    for (auto& w : wordDict) maxLen = max(maxLen, (int)w.size());
    vector<bool> dp(n + 1, false);
    dp[0] = true;
    for (int i = 1; i <= n; i++)
        for (int j = max(0, i - maxLen); j < i && !dp[i]; j++)
            if (dp[j] && words.count(s.substr(j, i - j))) dp[i] = true;
    return dp[n];
}

The general shape — dp[i] = combine over j < i of dp[j] ⊕ cost(j, i) — is partition DP. Other examples: Palindrome Partitioning II (min cuts), Perfect Squares, Minimum Cost For Tickets.

Family 3: Longest increasing subsequence (LIS)

A subsequence keeps order but may skip elements.

O(n²) — “ending at i”

def length_of_lis(nums):
    n = len(nums)
    dp = [1] * n                     # LIS ending exactly at i
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp, default=0)

O(n log n) — patience sorting

Keep tails[k] = the smallest possible tail of an increasing subsequence of length k + 1. tails is sorted, so each new element binary-searches its position.

from bisect import bisect_left

def length_of_lis(nums):
    tails = []
    for x in nums:
        i = bisect_left(tails, x)    # use bisect_right for non-decreasing
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x             # a smaller tail for length i+1
    return len(tails)

int lengthOfLIS(vector<int>& nums) {
    vector<int> tails;
    for (int x : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) tails.push_back(x);
        else *it = x;
    }
    return tails.size();
}

LIS in disguise:

• Russian Doll Envelopes: sort by width ↑ and height ↓ (so equal widths can't nest), then LIS on heights.
• Maximum Length of Pair Chain: LIS on intervals (or greedy by end).
• Minimum deletions to make sorted: n − LIS.
• Longest Bitonic Subsequence: LIS from the left + LIS from the right.
• Number of LIS: keep (length, count) pairs.

Family 4: Kadane-style “best ending here”

Maximum subarray and maximum product subarray are 1D DPs with O(1) state. See Arrays.

def max_product(nums):
    hi = lo = best = nums[0]
    for x in nums[1:]:
        candidates = (x, hi * x, lo * x)
        hi, lo = max(candidates), min(candidates)
        best = max(best, hi)
    return best

Family 5: State machines (stock problems)

When each day you're in one of a few statuses (holding a stock or not, in cooldown, transactions used), keep one DP value per status and write transitions between them.

          buy                 sell
  ┌─────┐ ─────►  ┌──────┐  ─────►  ┌──────┐
  │ rest│         │ hold │          │ sold │
  └─────┘ ◄───────└──────┘          └──────┘
     ▲      (stay)            cooldown  │
     └──────────────────────────────────┘

def max_profit_cooldown(prices):
    hold, sold, rest = float("-inf"), 0, 0
    for p in prices:
        hold, sold, rest = (
            max(hold, rest - p),     # keep holding, or buy (only from rest)
            hold + p,                # sell today
            max(rest, sold),         # do nothing; yesterday's sale ends cooldown
        )
    return max(sold, rest)

int maxProfit(vector<int>& prices) {
    long long hold = LLONG_MIN / 2, sold = 0, rest = 0;
    for (int p : prices) {
        long long h = max(hold, rest - p), s = hold + p, r = max(rest, sold);
        hold = h; sold = s; rest = r;
    }
    return max(sold, rest);
}

The whole stock family:

def max_profit_k(k, prices):
    buy = [float("-inf")] * (k + 1)
    sell = [0] * (k + 1)
    for p in prices:
        for j in range(1, k + 1):
            buy[j] = max(buy[j], sell[j - 1] - p)
            sell[j] = max(sell[j], buy[j] + p)
    return sell[k]

State machines also model Paint House (last color), Domino Tiling (profile of the last column), and Student Attendance Record (absences so far, trailing lates).

Choosing the look-back

Common mistakes

• Confusing “ending at i” with “among first i” and returning dp[n−1] instead of max(dp).
• Leading zeros in decode ways ("06" is not valid).
• Using bisect_right vs bisect_left incorrectly for strict vs non-strict LIS.
• Stock DP: updating states in place so today's buy feeds today's sell (use temporaries or tuple assignment).