1D DP (Including Kadane)

Dynamic programming is about turning exponential branching into linear passes by caching subproblem answers. In 1D DP, your state is indexed by a single dimension (index, step count, or prefix length), so the entire solution often collapses into a tight loop with rolling variables.

This module focuses on five recurring patterns: 1) Linear recurrence (ways/counts) -> Fibonacci-style transitions. 2) Take/skip (maximize/minimize) -> two rolling states. 3) Subarray DP (Kadane) -> best ending here. 4) Prefix segmentation (strings/amounts) -> dp over prefix length. 5) Monotone tails (LIS) -> DP + binary search compression.

Pattern A: Linear recurrence (Fibonacci-like)

Use when: each state depends on the previous 1-2 states and you only need counts.

Invariant: at index i, dp[i] is the correct count for the first i steps/items.

Skeleton:

if n <= base: return base
prev2, prev1 = dp[base-1], dp[base]
for i in base+1..n:
    cur = prev1 + prev2
    prev2 = prev1
    prev1 = cur
return prev1

Problems:

• climbing-stairs: classic Fibonacci recurrence.

Pattern B: Take/skip maximization

Use when: choose non-adjacent or limited choices with local constraints.

Invariant:

• prev1 is best answer up to i-1.
• prev2 is best answer up to i-2.

Skeleton:

prev2 = 0; prev1 = 0
for value in nums:
    take = prev2 + value
    skip = prev1
    cur = max(take, skip)
    prev2 = prev1
    prev1 = cur
return prev1

Problems:

• house-robber: linear take/skip.
• house-robber-ii: run take/skip twice (exclude first or last), take max.

Pattern C: Subarray DP (Kadane / sign-aware)

Use when: contiguous subarray optimization.

Invariant: bestEndingHere is the best subarray sum (or product) that must end at i.

Skeleton (sum):

best = nums[0]
cur = nums[0]
for i in 1..:
    cur = max(nums[i], cur + nums[i])
    best = max(best, cur)

Skeleton (product):

maxProd, minProd = nums[0], nums[0]
for x in nums[1:]:
    if x < 0: swap(maxProd, minProd)
    maxProd = max(x, maxProd * x)
    minProd = min(x, minProd * x)
    best = max(best, maxProd)

Problems:

• maximum-subarray: Kadane.
• maximum-product-subarray: track both max/min due to sign flips.

Pattern D: Prefix DP (segmentation / coin / decode)

Use when: you decide based on a prefix ending at i.

Invariant: dp[i] means s[:i] (or amount i) is solvable/optimal.

Skeleton (boolean segmentation):

set = dictionary
maxLen = max word length
DP[0] = true
for i in 1..n:
    for j in [i-maxLen..i):
        if DP[j] and s[j:i] in set:
            DP[i] = true; break

Skeleton (min coins):

DP[0] = 0
DP[i] = INF
for i in 1..amount:
    for coin in coins:
        DP[i] = min(DP[i], DP[i-coin] + 1)

Skeleton (decoding):

DP[0] = 1
DP[1] = (s[0] != '0')
for i in 2..n:
    if s[i-1] != '0': DP[i] += DP[i-1]
    if 10 <= s[i-2:i] <= 26: DP[i] += DP[i-2]

Problems:

• word-break: boolean segmentation with max word length pruning.
• coin-change: min coins with INF sentinel.
• decode-ways: 1-digit/2-digit transitions.

Pattern E: LIS via tails (DP + binary search)

Use when: longest increasing subsequence length only.

Invariant: tails[k] is the smallest possible tail value of a length k+1 subsequence.

Skeleton:

for x in nums:
    i = lower_bound(tails, x)
    if i == len(tails): append x
    else: tails[i] = x
return len(tails)

Problems:

• longest-increasing-subsequence: O(n log n) patience sorting.

When to use 1D DP (checklist)

• State can be indexed by a single position, prefix length, or step count.
• Transition depends on a fixed window of previous states (often 1 or 2).
• You can express the answer as an accumulation over indices.
• Greedy alone fails due to overlapping subproblems.

Common failures (checklist)

• Wrong base case for empty or length-1 input.
• Off-by-one in prefix DP (dp size = n+1).
• Not handling leading zeros in decode/word break cases.
• Forgetting to reset when using rolling arrays.
• Confusing subsequence (not contiguous) vs subarray (contiguous).

Why these problems fit

• Counting paths/ways -> linear recurrence (Climbing Stairs).
• Max under adjacency constraint -> take/skip (House Robber I/II).
• Best contiguous segment -> Kadane or sign-aware variant.
• Prefix segmentation/amount -> dp over prefix/amount.
• Longest increasing subsequence length -> DP compressed with binary search.