Repeated subproblems

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

DP is useful when different decision paths reach the same subproblem and future decisions depend only on a compact state. Identify repetition before adding a cache.

Work through an example

Taking or skipping earlier houses can both lead to deciding the same remaining suffix. Recursive solve(i) should be computed once rather than along every path.

Time and space complexity

Naive decision recursion exponential; one-dimensional DP O(n) states/time.

Why it works

All routes reaching the same state share the same future optimum under its contract.

Common mistakes

Different histories are mergeable only if state captures every future-relevant fact.
Caching an incomplete state gives wrong answers.

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