1D Dynamic Programming — Complete FAANG Interview Guide

Problem Statement#

You are a candidate preparing for a FAANG dynamic programming interview. You need to master the eight canonical 1D DP recurrences so that any new linear DP problem reduces to one you have already seen.

Constraints:

• 1 <= n <= 10^5 typical input size
• O(n) or O(n log n) time required for accepted solutions
• O(1) space achievable for most 1D DP via rolling variables
• Recurrence and base case must be derivable on a whiteboard in 5 minutes

Input:  A 1D problem (sequence, target, or count)
Output: Optimal value, count, or boolean reachable

Why This Problem Matters#

1D Dynamic Programming is the most heavily tested topic in dynamic programming interview rounds at Google, Meta, Amazon, Apple, Microsoft, and Netflix. Roughly forty percent of all DP interview questions reduce to one of eight 1D patterns, which means a small amount of pattern recognition unlocks a huge fraction of the question bank. Interviewers love 1D DP because it is small enough to write end-to-end in 30 minutes yet rich enough to probe state design, transition correctness, base cases, and space optimization.

Beyond DP FAANG screening, 1D DP shows up in real systems work — token bucket rate limiters use Kadane-style streaming maxima, search ranking uses LIS for monotone score chains, and billing pipelines use Coin Change variants for currency normalization. Mastering the templates below also sharpens your ability to identify when a recursive brute force has overlapping subproblems and can be flattened into an array.

This guide is the entry point for all 22 problems in the dsa-dp-1d series. Read it once, then attempt each problem and snap each one onto a pattern below. After 22 problems you will recognize a 1D DP within 30 seconds of reading any new statement.

The Core Insight#

Every 1D DP problem follows the same four-step derivation: define the state dp[i], write the transition that expresses dp[i] in terms of strictly smaller indices, set base cases, and decide iteration direction. The art is choosing the right state — usually either "answer ending at i" or "answer using first i items." Once the state is right, the transition writes itself.

The 8 Core 1D DP Patterns#

Pattern 1 — Fibonacci / Staircase#

State depends on the previous one or two values.

dp[i] = dp[i-1] + dp[i-2]

Problems: Climbing Stairs, Fibonacci Number, Min Cost Climbing Stairs, Tribonacci.

Pattern 2 — House Robber (Skip Adjacent)#

Cannot pick adjacent elements. Take or skip.

dp[i] = max(dp[i-1], dp[i-2] + nums[i])

Problems: House Robber, House Robber II circular, Delete and Earn.

Pattern 3 — Kadane (Max Subarray)#

Maximum subarray ending at index i — extend or restart.

curr = max(nums[i], curr + nums[i])
best = max(best, curr)

Problems: Maximum Subarray, Maximum Product Subarray, Circular Subarray Sum.

Pattern 4 — Coin Change (Unbounded Knapsack)#

Minimum coins to reach an amount — try every denomination.

dp[a] = min(dp[a - coin] + 1) for each coin

Problems: Coin Change, Coin Change II, Perfect Squares, Word Break.

Pattern 5 — LIS (Longest Increasing Subsequence)#

Either O(n^2) DP or O(n log n) patience sorting.

dp[i] = max(dp[j] + 1) for j < i where nums[j] < nums[i]

Problems: LIS, Russian Doll Envelopes, Longest Bitonic Subsequence.

Pattern 6 — Jump Game (Greedy DP)#

Track furthest reachable index — greedy collapses to O(n).

reach = max(reach, i + nums[i])

Problems: Jump Game, Jump Game II, Jump Game III.

Pattern 7 — Decode Ways / Counting#

Count ways given valid sub-choices.

dp[i] = dp[i-1] (if single digit valid) + dp[i-2] (if two digits valid)

Problems: Decode Ways, Number of Ways to Stay, Climbing Stairs with Constraints.

Pattern 8 — Palindromic Substrings#

Expand around center for substrings, 2D DP for subsequence.

expand(i, i) and expand(i, i+1)

Problems: Palindromic Substrings, Longest Palindromic Substring.

Visual Dry Run#

Climbing Stairs with n = 5 demonstrates the Fibonacci pattern.

Solution (Optimal)#

Space-optimized Fibonacci template — applies to Climbing Stairs, House Robber, and Decode Ways.

class Solution:
    def fib(self, n: int) -> int:
        if n < 2:
            return n
        prev2, prev1 = 0, 1
        for _ in range(2, n + 1):
            curr = prev1 + prev2
            prev2, prev1 = prev1, curr
        return prev1
 
    def rob(self, nums):
        prev2, prev1 = 0, 0
        for x in nums:
            prev2, prev1 = prev1, max(prev1, prev2 + x)
        return prev1
 
    def maxSubArray(self, nums):
        best = curr = nums[0]
        for x in nums[1:]:
            curr = max(x, curr + x)
            best = max(best, curr)
        return best

var fib = function(n) {
    if (n < 2) return n;
    let prev2 = 0, prev1 = 1;
    for (let i = 2; i <= n; i++) {
        const curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
};
 
var rob = function(nums) {
    let prev2 = 0, prev1 = 0;
    for (const x of nums) {
        const take = prev2 + x;
        prev2 = prev1;
        prev1 = Math.max(prev1, take);
    }
    return prev1;
};
 
var maxSubArray = function(nums) {
    let best = nums[0], curr = nums[0];
    for (let i = 1; i < nums.length; i++) {
        curr = Math.max(nums[i], curr + nums[i]);
        best = Math.max(best, curr);
    }
    return best;
};

Time: O(n) — single pass. Space: O(1) — two rolling variables replace the full dp array.

Complexity Reference#

Common Mistakes#

• Choosing the wrong state — for Kadane the state is "max ending at i" not "max in first i."
• Wrong base case for Fibonacci-type — dp[0] and dp[1] must match problem semantics.
• Forgetting to update best separately in Kadane — dp[i] is local, the answer is global.
• Forward versus backward iteration confusion in knapsack — unbounded goes forward, 0/1 goes backward.
• Off-by-one in Decode Ways — strings of length 0 and 1 need explicit base cases.

Interview Tips#

• Always say the four steps out loud — state, transition, base case, order.
• Sketch the dp array on the whiteboard for n = 5 before writing code.
• Mention the space optimization upgrade even if you write the O(n) version first.
• If stuck, recurse with memo first, then convert to bottom-up.
• Ask if mutation of input is allowed — sometimes you can DP in place.

Follow-up Questions#

• Can you reduce O(n) space to O(1)? — yes, when only the last k states are needed.
• Can you reconstruct the optimal sequence? — store parent pointers or backtrack the dp.
• What if values can be negative? — Kadane still works, but Coin Change does not.
• What if the array is circular? — solve linear twice, with and without first element.
• How do you handle very large n via matrix exponentiation? — Fibonacci becomes O(log n).

Key Takeaways#

• 1D DP covers eight recurring patterns — recognizing them is 90 percent of the battle.
• Always articulate state, transition, base case, and iteration order on the whiteboard.
• Most 1D DP problems space-optimize from O(n) to O(1) using two rolling variables.
• Kadane requires tracking both the local maximum ending at i and the global maximum.
• Coin Change loop direction encodes 0/1 versus unbounded — backward versus forward.
• LIS has both an O(n^2) DP and an O(n log n) patience sort solution — know both.
• Mastering this guide prepares you for 22 problems in the dsa-dp-1d series and any FAANG 1D DP question.

Problem Index#