stage t: 집 번호 t=0..n (n is dummy)

state i: 훔친 여부 i=0,1

ret func

f(t,i): 집 t~n-1에서 훔친 최대금액 g(t,i): 집 t~n-2에서 훔친 최대금액 (t=n-1에서는 안훔침)

BE: f(t,0) = max{f(t+1,1), f(t+1,0)} f(t,1) = money[t] + f(t+1,0)

BC: f(n,i) = 0 g(n-1, i) = 0

Obj: max{f(0,0), g(0,1)}

POO가 안맞는데??? → 경우 나눠서 두 번 계산하면 됨

1 0

0 1

1 -1