15 lines
599 B
Plaintext
15 lines
599 B
Plaintext
House Robber: money = [2, 7, 9, 3, 1]
|
|
=====================================
|
|
|
|
dp[k] = best total using only the first k houses
|
|
k [0, 1, 2, 3, 4, 5]
|
|
dp[k] [0, 2, 7, 11, 11, 12]
|
|
|
|
k=1 house worth 2: skip = dp[0] = 0, take = dp[0] + 2 = 2 -> dp[1] = 2
|
|
k=2 house worth 7: skip = dp[1] = 2, take = dp[0] + 7 = 7 -> dp[2] = 7
|
|
k=3 house worth 9: skip = dp[2] = 7, take = dp[1] + 9 = 11 -> dp[3] = 11
|
|
k=4 house worth 3: skip = dp[3] = 11, take = dp[2] + 3 = 10 -> dp[4] = 11
|
|
k=5 house worth 1: skip = dp[4] = 11, take = dp[3] + 1 = 12 -> dp[5] = 12
|
|
|
|
answer = 12 (houses worth 2, 9 and 1)
|