Dynamic Programming

Dynamic programming reuses the answer to the same remaining task reached through different choices. The difficult part is defining that task precisely; memoization or a table comes afterward.

1. Define a State That Determines the Future

Before coding, write the state in one sentence, the choices, base cases, recurrence, and which state answers the original question. Two calls may share a cached result only if their legal continuations and resulting value are identical.

For House Robber, let best(i) be the maximum obtainable from nums[i:], with no restriction inherited from earlier houses. Either skip house i, leaving best(i+1), or take it, forcing the next choice to start at i+2:

best(i) = max(best(i+1), nums[i] + best(i+2)), with best(i)=0 for i >= n.

The original answer is best(0). These choices cover every valid solution, and each child solves the same kind of remaining task. Passing the total already collected into the cache key would unnecessarily split equivalent states; return the best additional value instead.

2. Recipe: Memoize the Recurrence

from functools import cache

def rob(nums):
    @cache
    def best(i):
        if i >= len(nums):
            return 0
        return max(best(i + 1), nums[i] + best(i + 2))
    return best(0)

This is the reference chapter's memoization recipe: check a base case or cached answer, otherwise evaluate the recurrence and save it. Each of $O(n)$ indices is computed once with constant local work: $O(n)$ time, $O(n)$ cache and stack space. Long inputs can exceed a language's recursion limit; bottom-up iteration avoids that limit.

Allocate the cache per input, as the wrapper does here. If the underlying input changes, old entries are no longer valid. Zero, False, and negative numbers can be legitimate cached results; test membership rather than truthiness. Memoization also needs a terminating dependency relation: caching a result after recursion does not by itself break cycles.

3. Recognize the Main State Shapes

The following are applications of the same recurrence workflow, not separate recipes to memorize.

Base cases must match the question. For a grid maximum path, return the destination's value there and treat out-of-bounds choices as -inf; returning zero for an illegal move can incorrectly beat a valid negative path. For minimum coins, impossible positive amounts start at +inf. For subset sum, an empty subset achieves target zero. Complexity $O(nT)$ is pseudo-polynomial: it depends on the numeric target, not just the number of bits used to encode it.

For longest common subsequence, L(i,j) is the best length using a[i:] and b[j:]. An exhausted input returns zero. Equal characters give 1+L(i+1,j+1); otherwise take max(L(i+1,j), L(i,j+1)). Skipping characters is allowed; a substring would require contiguity and a different recurrence.

For longest increasing subsequence, a direct state is “best length ending at i”: inspect earlier smaller values for an $O(n^2)$ solution. The LIS problem also shows $O(n\log n)$ using minimum tail values and binary search; the tail array gives the length but is not necessarily an actual subsequence.

4. Tabulate, Then Reduce Memory Carefully

Choose an order in which every dependency is ready. House Robber's suffix recurrence runs right to left. A grid recurrence depending on the cell below and right runs bottom to top, right to left. LCS suffix states also fill backward in both indices.

For 0/1 subset sum, the one-dimensional update is:

def subset_sum(values, target):
    reachable = [False] * (target + 1)
    reachable[0] = True
    for value in values:
        for total in range(target, value - 1, -1):
            reachable[total] |= reachable[total - value]
    return reachable[target]

Assume nonnegative integer values and target. Descending totals read the previous item layer, so each item is used at most once. Ascending totals can read a value just updated by the same item, allowing reuse. This is why loop direction changes the problem.

For coin-change counting, coin-outer/amount-ascending counts unordered combinations; amount-outer/coin-inner counts ordered sequences. For coins [1,2] and amount 3, those answers are respectively 2 (1+1+1, 1+2) and 3 (also 2+1). Identify what constitutes a distinct answer before choosing loop order.

Rolling arrays preserve only the dependency layers still needed. House Robber needs two future results, so it can use $O(1)$ space; LCS length needs one row plus a saved diagonal, giving $O(\min(n,m))$ space. Time does not improve merely because storage shrinks.

5. Reconstruct a Solution and Count the Real Work

To return selected houses, a path, or a common subsequence, keep the decision that produced each state's optimum, or compare the already-computed child values while walking from the initial state. For House Robber, choose i when nums[i]+best(i+2) wins, then move to i+2; otherwise move to i+1. Define a tie rule if the question requires a particular optimum.

For LCS, equal characters are emitted and both indices advance; otherwise follow a child retaining the optimum. A full table supports reconstruction in $O(n+m)$ additional time. Discarding old rows may remove information needed for that walk; retain it when the actual solution is required.

Time is the sum of transitions examined per computed state, including slicing, hashing, copying and reconstruction. For partition DP, memoization does not turn an $O(n)$ choice loop into $O(1)$. Space includes stored states, the deepest active call chain, and output separately. A four-direction path with no revisits also needs the visited set in its state; (row,col) alone is not sufficient DP.

6. Key Takeaways

• Define best(i) as the best result for a specific remaining suffix; do not mix “ending at i” and “starting at i” recurrences.
• Use -inf or +inf for impossible optimization states; zero can be a valid answer and must not stand for “uncomputed.”
• Descending capacity prevents reuse in 0/1 selection; ascending capacity permits reuse.
• Retain decisions or enough table entries when the output must include a path or selected items.

Review Backtracking to derive choices, Recursion for call contracts, Topological Sort for dependency order, and Prefix Sums to make repeated segment-sum transitions constant-time.