Decision/reconstruction

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

An optimum value does not reveal the selected decisions. Store predecessors or recompute choices from the full DP table. Handle ties deterministically; multiple optimal outputs can exist.

Work through an example

The lab reconstructs [0,2,4] for [2,7,9,3,1]. When dp[i]==dp[i-1], it skips the last house; otherwise it takes i-1 and jumps back two.

Time and space complexity

O(n) reconstruction/O(n) table, plus selected-index output.

Why it works

Each reconstruction step preserves an attainable optimum for the remaining prefix.

Common mistakes

Compressed values alone may lose decision history.
A tie policy should not be mistaken for uniqueness.

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