1D DP Master Recap — FAANG Cheatsheet & Pattern Index

Problem Statement#

You have completed all 22 problems in the dsa-dp-1d series. This recap is your single reference page — every transition, every loop direction, every space optimization in one printable cheatsheet for the day before your dynamic programming interview.

Constraints:

• Targets all 8 canonical 1D DP patterns
• Must encode every transition compactly enough to memorize in 30 minutes
• Must distinguish 0/1 vs unbounded knapsack loop direction
• Must include LIS patience sort and Kadane variants

Input:  Any 1D DP problem
Output: The matching pattern, transition, and complexity in seconds

Why This Problem Matters#

The night before a Google, Meta, Amazon, Apple, or Microsoft dynamic programming interview, candidates do not need new content — they need a single dense reference that triggers recall. This recap exists for that moment. Every transition below has been chosen because it shows up repeatedly in FAANG screens and on-sites, and because confusing two transitions in the heat of an interview is the most common reason strong candidates fail DP rounds.

The eight patterns below cover roughly ninety percent of all 1D dynamic programming questions in the LeetCode top 150. The remaining ten percent are usually compositions — for example Word Break is reachability DP plus unbounded knapsack, and Russian Doll Envelopes is sort plus LIS. Recognizing the primitive patterns is the only durable way to handle novel DP problems under interview pressure.

Use this page as a printable last-mile cheatsheet, then reread the original guide if a transition feels foreign.

The Core Insight#

Every 1D DP collapses to the same template: define dp[i], write a transition over strictly smaller indices, fix base cases, and pick a loop direction. The eight patterns below differ only in which subproblems they reach back to and whether the loop runs forward or backward.

Pattern Reference#

Visual Dry Run#

LIS patience sort on [10, 9, 2, 5, 3, 7, 101, 18].

Solution (Optimal)#

The four most reused 1D DP templates in one place.

from bisect import bisect_left
 
class Solution:
    def maxSubArray(self, nums):
        best = curr = nums[0]
        for x in nums[1:]:
            curr = max(x, curr + x)
            best = max(best, curr)
        return best
 
    def coinChange(self, 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
 
    def lengthOfLIS(self, nums):
        tails = []
        for x in nums:
            i = bisect_left(tails, x)
            if i == len(tails):
                tails.append(x)
            else:
                tails[i] = x
        return len(tails)
 
    def canJump(self, nums):
        reach = 0
        for i, x in enumerate(nums):
            if i > reach:
                return False
            reach = max(reach, i + x)
        return True

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;
};
 
var coinChange = function(coins, amount) {
    const dp = new Array(amount + 1).fill(Infinity);
    dp[0] = 0;
    for (let a = 1; a <= amount; a++) {
        for (const c of coins) {
            if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
        }
    }
    return dp[amount] === Infinity ? -1 : dp[amount];
};
 
var lengthOfLIS = function(nums) {
    const tails = [];
    for (const x of nums) {
        let lo = 0, hi = tails.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (tails[mid] < x) lo = mid + 1;
            else hi = mid;
        }
        if (lo === tails.length) tails.push(x);
        else tails[lo] = x;
    }
    return tails.length;
};
 
var canJump = function(nums) {
    let reach = 0;
    for (let i = 0; i < nums.length; i++) {
        if (i > reach) return false;
        reach = Math.max(reach, i + nums[i]);
    }
    return true;
};

Time: Kadane O(n), Coin Change O(n*amount), LIS O(n log n), Jump Game O(n). Space: Kadane and Jump Game O(1), Coin Change O(amount), LIS O(n).

Key Insights#

Knapsack Loop Direction

• 0/1 each item once — loop amounts backward for j in range(target, w-1, -1).
• Unbounded item reusable — loop amounts forward for j in range(w, target+1).
• Count combinations — coins outer, amounts inner.
• Count permutations — amounts outer, coins inner.

LIS Patience Sort

• tails[i] is the smallest tail of any length-(i+1) increasing subsequence.
• bisect_left finds the position where the new element replaces or extends.
• The length of tails is the LIS length.

Kadane Extensions

• Product Subarray — track both min and max because negatives flip sign.
• Circular Subarray Sum — answer is max of normal Kadane and total minus min subarray.

Complexity Summary#

Common Mistakes#

• Confusing 0/1 vs unbounded knapsack loop direction — always state which one out loud.
• Forgetting dp[0] = 0 base case in Coin Change — leads to off-by-one infinity.
• Using bisect_right instead of bisect_left in LIS — gives non-strict increasing.
• Losing the global maximum in Kadane — dp[i] is local, must track best separately.
• Missing the circular case in House Robber II — must run linear DP twice.

Interview Tips#

• Memorize this cheatsheet the night before the interview.
• When given a new 1D DP, name the matching pattern out loud before coding.
• Always derive base cases from the smallest valid input — dp[0] and dp[1].
• State complexity before writing code so the interviewer can interrupt early.
• If the problem feels novel, try writing a brute-force recursion first — overlapping subproblems will reveal the DP.

Follow-up Questions#

• Can you space-optimize from O(n) to O(1)? — yes when only the last k states are reachable.
• Can you reconstruct the optimal sequence? — store parent pointers or backtrack through dp.
• What if values can be negative? — Kadane works, Coin Change does not without extra care.
• What if n is up to 10^9? — try matrix exponentiation for Fibonacci-type recurrences.
• How do you adapt LIS for non-strict increasing? — use bisect_right instead of bisect_left.

Key Takeaways#

• Eight patterns cover the vast majority of 1D DP interview questions at FAANG.
• Knapsack loop direction encodes 0/1 vs unbounded — backward vs forward.
• Kadane needs both a local max ending at i and a global best.
• LIS patience sort runs in O(n log n) and is the standard senior-level answer.
• House Robber II handles circularity by running linear DP twice.
• This recap is the single reference for the night before your DP interview.
• Pair with the dsa-dp-1d complete guide for full derivations and worked examples.

Problem Index#

Fibonacci — Climbing Stairs (01), Min Cost (02), Tribonacci (04).

House Robber — House Robber (03), Circular (04), Delete and Earn (05).

Kadane — Max Subarray (06), Max Product (07).

Unbounded Knapsack — Coin Change (08), Coin Change II (09), Perfect Squares (10).

Greedy — Jump Game (11), Jump Game II (12).

Counting DP — Decode Ways (13), Word Break (14), Target Sum (20).

LIS — LIS (15), Russian Doll Envelopes (16).

Palindrome — Palindromic Substrings (17), Longest Palindromic Subsequence (18).

0/1 Knapsack — Partition Equal Sum (19), Target Sum (20).