Dynamic Programming and State Definition

Dynamic programming has a reputation as the hardest interview topic, mostly because people meet it as a table of numbers with a formula attached and try to memorise the formula. The formula is the easy part. The part that decides whether you can solve an unfamiliar DP problem is the state definition: one precise sentence saying what a single entry in your table means. Get that sentence right and the transition usually writes itself. Get it vague (“dp[i] is the answer at i”) and you’ll spend the interview chasing off-by-one errors.

MIT’s 6.006 frames DP as a checklist it calls SRTBOT: subproblems, relations between them, a topological order to evaluate them in, base cases, the original problem expressed as a subproblem, and the time it all takes. This note follows the same order, starting from a recursion and ending with a table.

Start with a recursion that’s slow but correct

House Robber: houses in a row hold some amount of money, and you can’t rob two adjacent houses. What’s the most you can take? For [2, 7, 9, 3, 1] the answer is 12 (houses 0, 2 and 4).

Before any table, write the honest recursive answer. At house i, you either skip it or rob it, and robbing it means you skip i + 1:

def rob_plain(nums, i=0):
    """Best total from houses i..end."""
    if i >= len(nums):
        return 0
    return max(rob_plain(nums, i + 1),               # skip house i
               nums[i] + rob_plain(nums, i + 2))     # rob house i, skip i + 1

The docstring is the state definition, and it’s precise: the best total using only houses from i to the end. That’s the subproblem. The recursion is correct, but it recomputes the same suffixes over and over. On 30 houses, a call counter showed the cost:

plain: 88 calls: 4,356,617
memo:  88 32 calls

Same answer, 4,356,617 calls versus 32. The plain version grows like the Fibonacci numbers because each call spawns two more. Adding a cache (functools.lru_cache in Python, a Map in JavaScript) means each i is computed once, so there are only n + 2 distinct calls.

That memoised recursion is already dynamic programming. If you’re stuck in an interview, writing the recursion plus a cache is a complete, correct answer, and you can convert it to a table afterwards if asked.

Write the state as a sentence

The bottom-up version needs the state in table form. A common choice for prefix problems is:

dp[i] = the most money you can take from the first i houses (houses 0 to i - 1).

That “first i” wording means dp has n + 1 entries and dp[0] (no houses) is 0. It also means house i - 1 is the newest one considered in dp[i], which is where most off-by-one errors come from if you haven’t written the sentence down. The transition follows from the same skip-or-rob choice applied to that newest house:

def rob_table(nums):
    n = len(nums)
    dp = [0] * (n + 1)          # dp[i] = best total using only the first i houses
    if n:
        dp[1] = nums[0]
    for i in range(2, n + 1):
        dp[i] = max(dp[i - 1],                  # house i-1 not robbed
                    dp[i - 2] + nums[i - 1])    # house i-1 robbed, so i-2 is off limits
    return dp

On [2, 7, 9, 3, 1] the filled table, plus a walk backwards through it to recover which houses were chosen, prints:

dp = [0, 2, 7, 11, 11, 12] chosen house indexes = [0, 2, 4]

Read the table left to right and check each entry against the sentence. dp[2] = 7: from the first two houses, take the 7. dp[3] = 11: from the first three, take 2 and 9. dp[4] = 11: adding the house worth 3 doesn’t help, because robbing it means giving up the 9. dp[5] = 12: rob the last house (1) on top of dp[3]. To reconstruct the choice, walk backwards: wherever dp[i] differs from dp[i - 1], house i - 1 was robbed, so jump to i - 2.

The evaluation order matters too. dp[i] reads only dp[i - 1] and dp[i - 2], so filling left to right guarantees everything it needs is ready. That’s the “topological order” step: for any DP, you must fill states after the states they depend on.

Shrinking the table

Because each entry reads only the two before it, you don’t need the whole array:

def rob_rolling(nums):
    prev2, prev1 = 0, 0          # dp[i-2], dp[i-1]
    for x in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + x)
    return prev1

That returned 12, 4, 0 and 88 for [2, 7, 9, 3, 1], [1, 2, 3, 1], [] and the 30-house list. Time stays O(n), extra space drops from O(n) to O(1). The trade-off worth mentioning: with only two variables you can no longer walk back to find which houses were robbed. If the question asks for the choices, keep the table.

When loop order changes the meaning

Coin change problems show how a state definition can hide in the loop structure. Given coins [1, 2, 5], how many ways are there to make 5? Two near-identical programs give different answers:

def count_combinations(coins, amount):
    ways = [1] + [0] * amount        # ways[a] = multisets of the coins seen so far summing to a
    for c in coins:                  # coins outer
        for a in range(c, amount + 1):
            ways[a] += ways[a - c]
    return ways[amount]

def count_sequences(coins, amount):
    ways = [1] + [0] * amount        # ways[a] = ordered sequences summing to a
    for a in range(1, amount + 1):   # amount outer
        for c in coins:
            if c <= a:
                ways[a] += ways[a - c]
    return ways[amount]

combinations: 4  sequences: 9

With coins in the outer loop, by the time coin c is processed, ways[a] only counts combinations of coins up to c, so 1+2+2 and 2+1+2 can’t both be counted: coins are always added in a fixed order. That gives 4 (5, 2+2+1, 2+1+1+1, 1+1+1+1+1). With amounts outside, every coin can be the “last” coin of every amount, so different orderings count separately and you get 9. Neither program is buggy. They answer different questions, and the comment stating the state is the only thing that tells a reader which one was intended.

The minimum-coins version, Coin Change, uses the state “fewest[a] = fewest coins summing to exactly a”, with infinity for amounts that can’t be made:

def coin_change(coins, amount):
    INF = float("inf")
    fewest = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and fewest[a - c] + 1 < fewest[a]:
                fewest[a] = fewest[a - c] + 1
    return -1 if fewest[amount] == INF else fewest[amount]

It returned 3, -1, 0 and 20 for amounts 11 with [1, 2, 5], 3 with [2], 0 with [1], and 6249 with [186, 419, 83, 408]. The word “exactly” in the state matters: without it you’d be tempted to initialise everything to 0, and unreachable amounts would look free. A greedy “largest coin first” approach fails on coin sets like [1, 3, 4] with amount 6 (greedy picks 4+1+1, the answer is 3+3), which is why this needs DP at all.

Counting the cost

For any DP, time is the number of states times the work to compute one state. House Robber has n states with O(1) work each, so O(n). Coin Change has amount states and tries every coin at each, so O(amount × coins). Space is the size of the table, unless the transitions only look back a fixed distance, in which case you can keep just that window.

Interview practice: longest common subsequence

Given two strings, return the length of their longest common subsequence (characters in order, not necessarily adjacent). For "abcde" and "ace" the answer is 3. Define the state precisely, give the transition and base cases, and state the complexity.

Answer

State: dp[i][j] = length of the LCS of the first i characters of a and the first j characters of b. Using prefix lengths (rather than indexes) gives a natural base case: if either prefix is empty, the LCS is 0, so row 0 and column 0 are all zeros.

Transition, looking at the last characters of both prefixes, a[i - 1] and b[j - 1]:

• If they match, that character can end a common subsequence, so dp[i][j] = dp[i - 1][j - 1] + 1.
• If they don’t, at least one of them isn’t in the LCS, so drop one or the other and take the better: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]).

def lcs(a, b):
    m, n = len(a), len(b)
    # dp[i][j] = length of the LCS of a[:i] and b[:j]
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

print(lcs("abcde", "ace"), lcs("abc", "abc"), lcs("abc", "def"), lcs("", "abc"))

3 3 0 0

There are (m + 1) × (n + 1) states with constant work each, so O(m · n) time and space. Each row reads only the row above, so two rows of length n + 1 are enough if you only need the length, bringing space to O(min(m, n)) after swapping the shorter string into the inner loop. A point interviewers like to probe: in the mismatch case, a candidate sometimes writes dp[i - 1][j - 1] instead of the max of the two neighbours, which undercounts because it throws away both characters when only one needs to go. Test yourself on Longest Common Subsequence, then try House Robber and Edit Distance, writing the state sentence first each time.

Where to go next

• Data Structures and Algorithms interview questions
• DSA multiple-choice questions
• Backtracking and Safe Pruning Rules, for searches whose subproblems don’t overlap
• Algorithm Space Complexity and Auxiliary Storage, on memo tables and recursion depth
• MIT 6.006 Introduction to Algorithms (Spring 2020), lectures 15 to 18 cover dynamic programming