Min Houses — Knapsack ▶ PUSH DP
→
PUSH DP — citim dp[s], scriem în dp[s+g[i]] | from[] = DOAR reconstituire, nicio altă magie
Ce citim
PULL: dp[s − g[i]] ← stânga
PUSH: dp[s] ← curentul
Unde scriem
PULL: dp[s] ← curentul
PUSH: dp[s + g[i]] → dreapta
0/1 — direcție
PULL: s = G → g[i] (desc)
PUSH: s = G−g[i] → 0 (desc)
Unbounded — direcție
PULL: s = g[i] → G (asc)
PUSH: s = 0 → G−g[i] (asc)
Prevenire reutilizare
PULL: direcția descrescătoare
PUSH: direcția descrescătoare
from[] / prev[]
PULL: from[] = reconstituire
PUSH: from[] = reconstituire (identic)
Algorithm (C++) — PUSH DP
dp[s] — minim case pentru capacitate s
▮ dst (scriem)
▮ src (citim)
from[s] — STRICT reconstituire (traceback după ce dp e gata)