1D Dynamic Programming Problems: Classic Patterns

1D DP problems use a single index to define subproblems. Despite their simplicity, they show up constantly in interviews and teach the core DP skills: state definition, recurrence formulation, and space optimization.

The key insight with 1D DP: the answer for position i depends only on some previous positions (usually i-1, i-2, or a range). Once you internalize the patterns, you can tackle any 1D DP problem systematically.

Introduction

One-dimensional DP problems use a single index to define subproblems, making them the gateway to dynamic programming mastery. Despite their relative simplicity compared to multi-dimensional DP, 1D problems appear constantly in interviews and teach the core skills that apply across all DP: state definition, recurrence formulation, base case handling, and space optimization. Once you internalize these patterns, tackling more complex DP becomes systematic rather than intimidating.

These problems appear everywhere—climbing stairs, house robber, coin change, longest increasing subsequence—because many optimization problems naturally reduce to “considering elements up to index i” where dp[i] represents the optimal solution for that prefix. The space optimization from O(n) to O(1) using rolling variables is often possible and demonstrates deeper understanding of the recurrence structure.

This guide works through classic 1D DP problems with full implementations: climbing stairs with variable step sizes, house robber with circular street constraint, coin change (both minimum coins and count of combinations), longest increasing subsequence (O(n²) DP and O(n log n) binary search variant), and word break. Each problem includes the recurrence derivation, base case explanation, and space optimization where applicable. Interview questions cover Kadane’s algorithm relationship to DP, loop order importance in combination problems, and greedy vs DP trade-offs.

Climbing Stairs

def climb_stairs(n):
    """Ways to reach nth stair (can take 1 or 2 steps). O(n) time, O(1) space."""
    if n <= 2:
        return n

    prev2, prev1 = 1, 2  # dp[1]=1, dp[2]=2

    for i in range(3, n + 1):
        current = prev1 + prev2
        prev2, prev1 = prev1, current

    return prev1


def climb_stairs_with_variable_steps(n, steps):
    """
    Generalization: can take 1, 2, or up to 'steps' steps.
    dp[i] = sum(dp[i - step] for step in steps if i >= step)
    """
    dp = [0] * (n + 1)
    dp[0] = 1

    for i in range(1, n + 1):
        for step in steps:
            if i >= step:
                dp[i] += dp[i - step]

    return dp[n]

House Robber

def house_robber(nums):
    """
    Max money robbed without robbing adjacent houses.
    dp[i] = max(dp[i-1], dp[i-2] + nums[i])
    """
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]

    prev2, prev1 = nums[0], max(nums[0], nums[1])

    for i in range(2, len(nums)):
        current = max(prev1, prev2 + nums[i])
        prev2, prev1 = prev1, current

    return prev1


def house_robber_circular(nums):
    """Robber with circular street - can't rob first and last house."""
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]

    # Exclude last house or exclude first house
    def rob_linear(houses):
        prev2, prev1 = 0, 0
        for money in houses:
            current = max(prev1, prev2 + money)
            prev2, prev1 = prev1, current
        return prev1

    return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))

Coin Change

def coin_change(coins, amount):
    """Min coins needed to make amount (unlimited coins)."""
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1


def coin_change_ways(coins, amount):
    """Number of ways to make amount with unlimited coins."""
    dp = [0] * (amount + 1)
    dp[0] = 1

    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] += dp[i - coin]

    return dp[amount]

Longest Increasing Subsequence (1D Variant)

def lis_length(nums):
    """Find LIS length - O(n²) DP, can be O(n log n) with binary search."""
    if not nums:
        return 0

    n = len(nums)
    dp = [1] * n  # dp[i] = LIS length ending at index i

    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)


def lis_binary_search(nums):
    """O(n log n) LIS using patience sorting."""
    import bisect

    tails = []
    for num in nums:
        pos = bisect.bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)
        else:
            tails[pos] = num

    return len(tails)

Word Break

def word_break(s, word_dict):
    """Can string s be segmented into dictionary words?"""
    word_set = set(word_dict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True

    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break

    return dp[n]

Common 1D DP Patterns

Problem	Recurrence	Key Insight
Climb Stairs	dp[i] = dp[i-1] + dp[i-2]	Add current step to previous
House Robber	dp[i] = max(dp[i-1], dp[i-2] + nums[i])	Take or skip current
Coin Change	dp[i] = min(dp[i], dp[i-coin] + 1)	Try each coin
LIS	dp[i] = max(dp[j] + 1) for j < i	Compare with smaller elements
Word Break	dp[i] = OR(dp[j] AND s[j:i] in dict)	Split at valid boundaries

Space Optimization Patterns

# Full O(n) space
dp = [0] * (n + 1)
dp[i] = dp[i-1] + dp[i-2]

# Optimized to O(1)
prev2, prev1 = 0, 1  # corresponds to dp[-1], dp[0]
for i in range(1, n + 1):
    current = prev1 + prev2
    prev2, prev1 = prev1, current

When to Use 1D DP

Use 1D DP when:

• Problem can be expressed as “considering elements up to index i”
• Recurrence only depends on previous values (not the full history)
• You’re asked to optimize linear progression problems

Common interview triggers:

• “Maximum/Minimum subsequence…”
• “Ways to achieve…”
• “Can you partition/split…”
• “Longest increasing/decreasing…“

1D DP Trade-Offs

Aspect	Top-Down (Memoized)	Bottom-Up (Tabulation)	Space-Optimized
Time	O(n) with memoization	O(n)	O(n)
Space	O(n) call stack + table	O(n) table	O(1) to O(k)
Debugging	Stack trace shows path	Full table for inspection	Harder to debug
Initialization	Lazy, compute on demand	Must init all states	Same as bottom-up
Recurrence access	Natural recursive	Must respect order	Must respect order

Top-down: easier to write recursively, good when recurrence doesn’t need all subproblems. Bottom-up: explicit control over computation order, better for production. Space-optimized: use when recurrence only needs last k states, not the full history.

1D DP State Transition Flow

graph TD
    START["Input Array"] --> INIT["Initialize dp array"]
    INIT --> BASE["Set base cases\ndp[0], dp[1]"]
    BASE --> LOOP["For i = 2 to n"]
    LOOP --> TRANS["Apply recurrence:\ndp[i] = f(dp[i-1], dp[i-2], ...)"]
    TRANS --> VALID{"Valid state?"}
    VALID -->|"Yes"| STORE["Store dp[i]"]
    STORE --> NEXT["i = i + 1"]
    NEXT --> LOOP
    VALID -->|"No"| ADJUST["Adjust recurrence\nor boundary conditions"]
    ADJUST --> TRANS
    LOOP -->|"i > n"| DONE["Return dp[n] or\noptimized result"]

    DONE2["Space Optimization:\nKeep only needed previous states"]
    STORE --> DONE2

For 1D DP, each state represents the solution to a subproblem ending at that index. The recurrence tells you how to build dp[i] from earlier states.

Production Failure Scenarios and Mitigations

1D DP implementations break in specific ways once they hit production traffic.

O(n²) subproblem explosion

A poorly chosen recurrence can cause each state to re-compute the same subproblems multiple times. If your recurrence calls dp[i-1] and dp[i-2] without memoization in a naive recursive implementation, it effectively becomes exponential.

The exponential blowup happens when a recurrence that looks linear on paper, like Fibonacci’s naive recursive form, is implemented without caching. Each call to fib(n) branches into two calls, creating a binary tree of size O(2^n). This is what separates the O(n) memoized version from the O(2^n) naive version. A simple instrumented Fibonacci shows the difference clearly: memoized Fibonacci computes each value once and stores it, giving exactly n function calls for fib(n). Naive Fibonacci without caching recomputes the same values exponentially many times, and the subproblem count grows like a binary tree rather than a linear chain.

The silent failure pattern appears when the implementation passes small test cases but fails on large ones. At n=20, the naive recursive Fibonacci still finishes in milliseconds. At n=50, it takes seconds. At n=100, it would take longer than the age of the universe. The problem looks correct because it returns the right answer for small inputs, but the algorithm is running in exponential time while appearing linear. Always instrument subproblem counts during development. If you see counts growing faster than the expected complexity curve, something is recomputing instead of caching. A simple counter that increments each time the recurrence is evaluated will catch this immediately.

Fix: Use bottom-up tabulation with explicit state ordering. Verify your implementation’s time complexity matches theory by instrumenting subproblem counts.

The exponential blowup happens when a recurrence that looks linear on paper, like Fibonacci’s naive recursive form, is implemented without caching. Each call to fib(n) branches into two calls, creating a binary tree of size O(2^n). This is what separates the O(n) memoized version from the O(2^n) naive version. The fix is straightforward in code but the symptom is subtle: a problem that passes small test cases fails silently on large ones because the algorithm is running in exponential time while looking linear. Always instrument subproblem counts during development. If you see counts growing faster than the expected complexity curve, something is recomputing instead of caching.

Space optimization breaking when recurrence assumptions change

You implement space optimization keeping only the last two states because the recurrence only uses dp[i-1] and dp[i-2]. Then someone modifies the recurrence to use dp[i-3] for a new feature, and the optimized version silently produces wrong results.

Space optimization is a compile-time assumption about the recurrence structure. When you optimize to O(1) space by keeping only prev2 and prev1, you’re asserting that the recurrence never needs anything older than dp[i-2]. This assertion lives in the code as a constant, not as a validated property. When the recurrence changes, the assertion becomes false, but the code still compiles and runs. It just gives wrong results. The optimized implementation looks correct because it runs fine on the full test suite. It just silently produces wrong answers in production when someone adds a feature that changes the recurrence to use dp[i-3].

The concrete example: your house robber recurrence is dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Space optimization keeps only two variables. Then a new requirement arrives: you cannot rob houses more than k positions apart. The recurrence becomes dp[i] = max(dp[i-1], dp[i-2] + nums[i], dp[i-3] + nums[i-1]) or similar. The optimized code still keeps only two variables, but now needs three. The result is a wrong maximum that silently passes tests because the test suite didn’t include the new constraint.

Fix: Keep a full-table implementation in tests as a reference. When modifying recurrence relations, compare full-table output against optimized output for all test cases. Never change a recurrence without running both versions.

The danger with space optimization is that it’s a compile-time assumption about the recurrence. When the recurrence changes, new feature, new constraint, new requirement, the space optimization often survives as dead code silently producing wrong answers. The optimized implementation looks correct because it runs fine. It just gives wrong results. This is why regression test suites that compare optimized against full-table implementations catch this class of bugs. Never change a recurrence without running both versions.

Integer overflow in DP with large values

DP for problems like “number of ways to climb 10⁹ stairs” produces astronomically large numbers that overflow 32-bit integers. In languages with fixed-size integers, this causes silent wraparound and wrong answers.

Integer overflow in DP is particularly insidious because it produces silently wrong answers without crashing. A result that should be 50 digits wraps around to a small positive number, and the algorithm returns what looks like a plausible answer. The problem appears in any DP that counts ways rather than minimizing or maximizing. The number of ways to climb 100 stairs with variable steps grows exponentially. For n=1000 with steps [1,2,3,5], the result has hundreds of digits. In a 32-bit integer, it wraps to a small positive number. In a 64-bit integer, it still wraps, just less quickly. The algorithm finishes, returns a value, and that value is wrong.

The fix depends on the language. Python’s native arbitrary-precision integers eliminate the problem entirely at a performance cost that is usually negligible for practical input sizes. In Go or Java, use 64-bit integers and validate that results stay within bounds. In C/C++, use a big-integer library or apply modular arithmetic. When using modulo, remember that it changes the semantics. Comparisons of “which solution is larger” no longer work, and operations like “count paths modulo 1,000,000,007” are only valid when the problem explicitly allows it. For problems where the modulo is not specified, overflow still occurs. Always check the problem constraints for result size expectations before choosing a data type.

Integer overflow in DP is particularly insidious because it produces silently wrong answers without crashing. A result that should be 50 digits wraps around to a small positive number, and the algorithm returns what looks like a plausible answer. The fix depends on the language. Python’s native arbitrary-precision integers eliminate the problem entirely at a performance cost. In Go or Java, use 64-bit integers and validate that results stay within bounds. In C/C++, use a big-integer library or apply modular arithmetic. When using modulo, remember that it changes the semantics. Comparisons of “which solution is larger” no longer work, and operations like “count paths modulo 1,000,000,007” are only valid when the problem explicitly allows it.

Off-by-one in base case setup

A dp array where dp[0] should represent an empty solution but gets initialized to 1 for the “one way to climb zero stairs” case. When combined with a recurrence that accesses dp[i-1], the off-by-one in base cases produces wrong results for larger inputs.

The dp[0] = 1 case represents “one way to do nothing” — one way to climb zero stairs, one way to make amount zero, one way to decode an empty string. This base case anchors the recurrence. If dp[0] is wrong, the error compounds through every subsequent state. For climbing stairs with recurrence dp[i] = dp[i-1] + dp[i-2], the trace for n=3 goes: dp[0] = 1, dp[1] = 1, dp[2] = dp[1] + dp[0] = 2, dp[3] = dp[2] + dp[1] = 3. If dp[0] were initialized to 0 instead of 1, dp[2] would be 1 instead of 2, and dp[3] would be 2 instead of 3. The off-by-one in the base case produces a wrong answer for every n greater than 1.

Testing strategy: write test cases for n=0, n=1, n=2, n=3 and verify against known results. The n=0 case is particularly important because it forces you to handle the empty solution correctly. Trace through by hand for n=3 to ensure base cases and recurrence interact correctly. For coin change, test amount=0 (should return 1 — one way to make zero amount using no coins), amount=1, amount=2. For decode ways, test empty string, single digit, double digit. These small cases catch base case errors before they compound.

Quick Recap Checklist

• dp[i] represents answer for subproblem ending at index i
• Recurrence shows how dp[i] relates to smaller states
• Handle base cases (dp[0], dp[1]) correctly
• Consider space optimization when recurrence only uses limited previous states
• For O(n²) problems, check if O(n log n) alternatives exist

Observability Checklist

Track 1D DP implementations to catch performance and correctness issues early.

Core Metrics

Track these in every 1D DP implementation to establish a performance baseline and catch regressions.

• Subproblem count — should match theoretical complexity (e.g., O(n) for Fibonacci, O(n²) for LIS DP). Instrument a counter in the recurrence and compare against the expected curve. For O(n) problems, subproblem count should be exactly n or n+1. For O(n²) problems like LIS, it should be n*(n-1)/2. Any deviation means the recurrence is recomputing instead of reusing.
• DP array size and growth rate — monitor how memory grows with increasing n. A 1D DP should grow linearly with n. If memory usage grows faster than linear, the state space has unexpectedly expanded. This happens when the recurrence is changed to use more previous states without updating the space optimization.
• Time per subproblem computation — track the wall-clock time per subproblem. Consistent per-subproblem time that suddenly spikes indicates cache pressure from memory allocation patterns or GC overhead in managed languages. For memoized implementations, spikes in specific subproblem computation time can indicate hash collisions or cache thrashing.
• Cache hit rate in recurrence lookups — for memoized implementations, log cache hits vs misses to verify the overlap assumption. Low hit rate means the problem may not be a good DP fit, or the recurrence is exploring an unexpectedly large fraction of the state space. A hit rate below 0.5 suggests the memoization is not providing the expected benefit.
• Memory footprint of DP table — track allocated vs used entries. A ratio far below 1.0 suggests the state space is sparser than expected. For problems where not all states are reachable, sparse memoization with a dictionary may be more appropriate than a full array.

Health Signals

These signals indicate an implementation is drifting from expected behavior before a full failure occurs.

• Subproblem count exceeding O(n) or O(n²) for expected input sizes — the recurrence is recomputing states instead of reusing cached results. This is the clearest signal of a memoization bug. Check that the cache key includes all parameters that affect the recurrence, and that cache lookups are actually storing results.
• DP table size growing faster than linear — a linear DP should never grow super-linearly in subproblem count. This is a state explosion indicator. It means the recurrence is depending on more previous states than expected, or the space optimization is no longer valid.
• Execution time > expected by more than 2x — investigate whether the recurrence is hitting a worst-case pattern or the memory allocator is fragmenting. For O(n) problems, execution time should scale linearly with n. A 2x degradation at 10x input size suggests something is wrong.
• Memory usage approaching limits for large n — set a memory budget alert before hitting OOM. For 1D DP, O(n) space should be predictable. If memory usage is approaching limits at smaller n than expected, the state space may have expanded or the space optimization may have been lost.

Alerting Thresholds

Set these thresholds in production monitoring to catch issues before they escalate to service failures.

• Subproblem count > 2x theoretical expectation — possible recurrence bug, algorithmic complexity attack, or a change in input distribution that makes the problem harder. Investigate immediately. A 2x spike in subproblem count for the same input size is almost always a bug, not a workload change.
• DP table memory > 500MB for single problem — OOM risk on instances with limited memory. For 1D DP, a 500MB table means n is around 500 million for 8-byte values. This is larger than most reasonable inputs. If this threshold fires, consider space optimization or rejecting large inputs before they reach the DP.
• Execution time p99 > 1s for n < 10⁶ — 1D DP at this scale should run in milliseconds. A p99 above 1s suggests pathological input or resource contention. If the input is legitimately large, consider whether a more efficient algorithm exists. If the input is small, investigate the system-level causes.
• Any silent overflow in result values — detect wraparound by validating result magnitude against expected bounds for known inputs. Silent overflow produces plausible-looking wrong answers. For counting problems, validate that results are non-negative and within expected ranges for the input size.

Distributed Tracing

For services that run DP as part of a larger pipeline, tracing helps correlate DP performance with downstream effects and identify which inputs cause problems.

• Trace DP computation with subproblem count as span attribute — each DP run should produce a span tagged with dp.subproblem_count and dp.state_dimensions. This makes it easy to filter traces by problem size and find the inputs that caused high subproblem counts.
• Include n and recurrence depth in trace metadata — dp.input_size and dp.recurrence_depth help distinguish between different DP problem types in the same service. Recurrence depth indicates how many previous states the recurrence depends on, which helps identify which optimization is valid.
• Correlate slow DP runs with large input sizes or memory pressure — slow traces often correlate with high memory usage or large n. Adding both to the trace context makes root cause faster to find. If a slow trace shows large n but reasonable subproblem count, the issue is memory-bound. If it shows expected n but high subproblem count, the issue is algorithmic.

Security Notes

DP implementations have specific security concerns worth thinking about.

Algorithmic complexity attacks on DP recurrence

If user-controlled input affects the number or complexity of subproblems, an attacker can craft inputs that cause the DP to compute far more work than expected. A recurrence that’s O(n²) in the worst case gets weaponized against implementations assuming O(n) average case.

The attack surface is larger than it first appears. For a standard 1D DP like LIS, the subproblem count is O(n^2) in the worst case. An attacker submitting a strictly increasing sequence to an LIS implementation that assumes average-case faster than worst-case causes the algorithm to do far more work than the average case. This matters for services where user input controls n. A service that accepts a sequence of length n without bounds is vulnerable to an n=100,000 input producing 10 billion subproblem computations instead of the expected n log n.

Setting hard limits on n is the primary defense. Monitor subproblem counts and alert when computation exceeds the expected bound by a large factor. The alert is your early warning system. If you expect O(n log n) and see O(n^2), something is wrong. Validate input ranges before starting DP. For LIS, a sequence of length 100,000 should be rejected or processed with a different algorithm. The goal is to make the attacker cost higher than the service cost.

The attack surface is larger than it first appears. For a standard 1D DP like LIS, the subproblem count is O(n^2) in the worst case. An attacker submitting a carefully crafted sequence could force the algorithm to do far more work than the average case. This matters for services where user input controls n. Set hard limits on n, instrument subproblem counts, and alert when computation exceeds the expected bound by a large factor. The alert is your early warning system.

Memoization table DoS via hash collision

If the memoization uses a hash table internally and the input keys are attacker-controlled, the attacker can craft keys that all hash to the same bucket, causing O(n²) lookup time instead of O(1).

Hash collision attacks exploit the worst-case guarantee of hash tables. While average-case lookup is O(1), worst-case is O(n) when all keys collide. An attacker who knows your hash function can submit inputs that produce identical hash values, degrading your memoization from O(n) time complexity to O(n^2). For a memoized DP where the cache key is derived from user input, this is a real vulnerability. The attack requires knowing the hash function, but many implementations use standard library hash functions that are publicly documented.

Python’s dict uses SipHash, which is designed to resist this. If you’re using a custom hash function or a language without DoS-resistant hashing, you’re potentially vulnerable. For memoized DP where the cache key is derived from user input, audit the hash function. For cryptographic contexts, use constant-time comparison for memoized values to prevent timing attacks on the cache lookup. The fix is straightforward: use the language runtime’s default hash map, which for Python means dict, and for Go means map. Both use DoS-resistant hash functions.

Hash collision attacks exploit the worst-case guarantee of hash tables. While average-case lookup is O(1), worst-case is O(n) when all keys collide. An attacker who knows your hash function can submit inputs that produce identical hash values, degrading your memoization from O(n) to O(n²). Python’s dict uses SipHash, which is designed to resist this. If you’re using a custom hash function or a language without DoS-resistant hashing, you’re potentially vulnerable. For memoized DP where the cache key is derived from user input, this is worth auditing.

Space complexity bombs causing OOM

A 1D DP problem where the recurrence unexpectedly requires O(n²) space (someone modified it to use a matrix instead of a vector) can exhaust memory.

The space complexity bomb happens when the recurrence changes to depend on more previous states than the current space optimization accounts for. A recurrence that originally needed only dp[i-1] and dp[i-2] gets modified to need dp[i-1] through dp[i-k] for larger k. The space optimization that kept only two variables is now insufficient, but the code still compiles. It silently produces wrong answers by reading uninitialized or stale values from the compact state vector.

When recurrence unexpectedly requires O(n²) space, the result is an out-of-memory failure. This happens when someone adds a feature that changes the recurrence to use a sliding window of previous states. The code allocates a full O(n) table when it should allocate O(k) for a fixed window, but the space optimization was removed or changed without updating the allocation. Monitor memory growth rate during DP computation. A linear DP should grow linearly with n. If memory usage grows quadratically, the state space has unexpectedly expanded. Set hard limits on DP table size and use streaming approaches for very large n when possible.

Interview Questions

Further Reading

Books and Courses

• “Introduction to Algorithms” (CLRS) — Chapters 15 (Dynamic Programming) and 25 (All-Pairs Shortest Paths) provide rigorous theoretical foundations with formal proofs of optimal substructure. The chapter on DP is the standard reference for understanding the theoretical basis: optimal substructure, overlapping subproblems, and the relationship between DP and memoization. Worth reading even if you already know DP, because it formalizes why the technique works.
• “Algorithm Design Manual” by Skiena — Chapter 8 (Dynamic Programming) has an excellent problem-driven approach with a catalog of DP problems and practical war stories from real implementations. Skiena emphasizes recognizing DP patterns and knowing when to apply them, which is more useful for interviews than theoretical proofs.
• “Cracking the Coding Interview” — DP problems in the chapter on recursion and dynamic programming, with step-by-step walkthroughs and interview-specific tips. The interview focus means it covers the most common DP patterns and how to explain your approach in an interview setting.
• “Algorithmic Adventures” (Kleinberg) — Chapter 9 covers DP with an emphasis on problem-solving strategies and how to derive recurrences from first principles. Kleinberg focuses on the creative process of deriving recurrences, which is the hardest part of DP for most people.

Online Resources

• LeetCode 1D DP Problem Set — Curated list: Climbing Stairs (70), House Robber (198), Coin Change (322), Decode Ways (91), Maximum Subarray (53), Word Break (139), Longest Increasing Subsequence (300). Each problem has community discussion with multiple approaches. The problem set is organized by difficulty and covers the most common interview patterns. The community solutions show different implementations and optimization techniques.
• GeeksforGeeks DP Tutorial — Comprehensive guide with categorized problems and complexity analysis, including practical C++ and Java implementations. The categorized approach helps when you know the problem type but not the specific problem. The implementations are often more optimized than typical interview code because they come from competitive programming backgrounds.
• MIT OpenCourseWare 6.006 — Lectures on DP including Fibonacci, shortest paths, and edit distance with lecture notes and problem sets. The lecture notes provide the theoretical context that most tutorials skip. Watching the lectures and reading the notes gives a deeper understanding than just solving problems.
• CP-Algorithms (E. Mendeleev) — Russian competitive programming community wiki with detailed DP implementations optimized for large inputs. The implementations here are tuned for performance and handle edge cases that typical interview code ignores. Useful for understanding how DP performs at scale.

Advanced Topics

The five topics below venture into territory that rarely appears in standard interviews but comes up constantly in competitions and system design. What changes each time is how you represent state or how the recurrence behaves — not just different parameters, but a different kind of recurrence altogether.

• DP with Bitmasking — When the state space includes subsets, 1D DP extends to DP over subsets (e.g., traveling salesman problem). The state becomes a bitmask, and transitions iterate over set bits. Complexity is O(n 2^n), practical for n up to 20. The bitmask encodes which elements have been used, and the recurrence iterates over which element to add next. This transforms a problem that looks exponential into a polynomial-time DP over subsets.
• Digit DP — A specialized 1D DP technique for counting numbers with certain digit properties in a range. Used for problems like “count numbers divisible by 7 between 1 and 10^9.” The state tracks position and carry/remainder. Digit DP processes numbers digit by digit, maintaining state across positions. This is useful for problems where the input is a range of numbers rather than a single number.
• DP on Trees — When the “index” becomes a tree node instead of a linear position, recurrences follow edges rather than indices. Post-order traversal replaces linear iteration. The state for a node depends on states for its children, and the recurrence combines child states in ways specific to the problem. Tree DP appears in problems like tree diameter, independent set on trees, and segment tree lazy propagation.
• Convex Hull Trick — Optimizing DP recurrences of the form dp[i] = min(dp[j] + A[j] * i) where A[j] is monotonic. Reduces O(n^2) to O(n log n) or O(n) using the convex hull property. The convex hull trick applies when the recurrence can be rewritten as a linear function of i for each j, and the optimal j moves monotonically as i increases. This is common in optimization problems like line scheduling or knapsack variants.
• Divide and Conquer DP Optimization — When dp[i] = min(dp[j] + cost(j+1, i)) and the cost function satisfies the quadrangle inequality, the optimal split point is monotonic. Knuth optimization applies when cost is quadrangle-inequality-compliant, reducing O(n^2) to O(n log n). The quadrangle inequality is a mathematical property of the cost function that enables this optimization. Not all cost functions qualify, but when they do, the speedup is significant.

Conclusion

Once you’re comfortable with 1D DP, 2D DP is the next step. 1D trains you to think about one prefix. 2D asks you to track two at once — like LCS comparing two strings, or matrix chain multiplication where your state spans a range. Same core idea, bigger table.

For the next step, see /blog/technical/2d-dp-problems/.