Reducing state storage

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

Reduce storage only after deriving dependencies. If a transition needs two prior values, rolling variables can replace the table. This preserves the optimum value but normally sacrifices easy reconstruction.

Work through an example

Before each house x, older and previous hold the two preceding prefix optima. Simultaneous assignment updates them from old values.

Time and space complexity

O(n) time/O(1) variables for rob_compact; output decisions are not provided.

Why it works

previous is the optimum for all houses already processed.

Common mistakes

Updating older before using its old value corrupts the transition.
Space reduction may complicate debugging and reconstruction.

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