State, transition, and base cases

What is dynamic programming?

Dynamic programming, or DP, solves a problem by saving answers to smaller problems and reusing them. A state describes one smaller problem. A recurrence tells you how its answer depends on earlier answers. One-dimensional DP stores those states using one position or quantity, such as a step number.

Example: If you can climb 1 or 2 steps, ways(3) = ways(2) + ways(1): every route to step 3 ends by coming from step 2 or step 1. Save each smaller answer rather than recomputing it.

Helpful before this chapter

If these ideas are new, begin with:

Arrays and dynamic arrays Recursion

Understand the idea

State defines meaning; transition considers all valid final choices; base cases ground the recurrence. For first-i-house DP, either skip house i-1 or take it with the first i-2 houses. A different one-index state appears in increasing subsequences: dp[i] is the best length ending at i, initialized to 1. For each earlier j with values[j]<values[i], consider dp[j]+1; the final answer is max(dp). This is an ending-position state, unlike the house example’s prefix optimum, so copying the house recurrence would be incorrect.

Work through an example

[2,7,9] gives dp=[0,2,7,11]. At i=3, max(dp[2],dp[1]+9)=max(7,11).

Time and space complexity

O(n) time/O(n) table; empty selection permits optimum zero on all-negative values.

Why it works

dp[i] is exactly the best valid nonadjacent total among the first i houses.

Common mistakes

Mixing prefix and suffix indices changes the recurrence.
dp[1] must respect the empty-choice policy.

Chapter lab · Python implementation

Dynamic programming solves a state once and reuses its result. The running problem maximizes money from nonadjacent houses, permitting an empty choice. Define dp[i] as the optimum for the first i houses, not a vague score. Decisions reconstruct one optimum; space reduction is a separate tradeoff.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

from functools import lru_cache

def rob(values):
    dp=[0]*(len(values)+1)
    if values: dp[1]=max(0,values[0])
    for i in range(2,len(values)+1):
        dp[i]=max(dp[i-1],dp[i-2]+values[i-1])
    chosen=[]; i=len(values)
    while i>0:
        if dp[i]==dp[i-1]: i-=1
        else:
            chosen.append(i-1); i-=2
    return dp[-1],list(reversed(chosen))

def rob_memo(values):
    @lru_cache(None)
    def solve(i):
        if i>=len(values): return 0
        return max(solve(i+1),values[i]+solve(i+2))
    return solve(0)

def rob_compact(values):
    older,previous=0,0
    for x in values:
        older,previous=previous,max(previous,older+x)
    return previous

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

assert rob([2,7,9,3,1])==(12,[0,2,4])
assert rob([])==(0,[]) and rob([-3,-2])==(0,[])
for a in [[],[5],[2,1,1,2],[-1,3,-2,4]]:
    assert rob(a)[0]==rob_memo(a)==rob_compact(a)

CHECK YOUR UNDERSTANDING