Tabulation and iteration order

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

Tabulation computes dependencies before consumers. A bottom-up order is valid when every transition reads already-final states. It avoids recursion limits and makes table contents inspectable.

Work through an example

For rob, increasing i works because only i-1 and i-2 are read. For coin amount DP, increasing amount works when coins are positive.

Time and space complexity

O(states×transitions-per-state) time; table space follows state count.

Why it works

Every table entry read by the current transition has already been computed correctly.

Common mistakes

Loop order can change combination counting into permutation counting.
Cyclic dependencies require another model or iteration argument.

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