Leetcode 198 - House Robber

Problem#

給你一個整數陣列 M[i] 代表第 $i$ 間房子的價值，你今天是小偷要去偷錢，但是有個限制是不能連續偷(偷第 $i$ 間，第 $i-1$ 和 $i+1$ 都不能偷)，否則會被抓到，問你最大能偷多少?

對於 $1$ 到 $i$ 能偷的總價值，假如你挑了第 $i$ 間房子，那一定是和第 $i-2$ 間的房子加總起來($W[i]+W[i-2]$)；如果不挑 $i$ 那必定是 $i-1$ ($W[i-1]$)，而要求兩者最大，所以取 max

W[1...3] = 
             挑自己      不挑自己
dp(2) = max(M[2]+M[2-2], M[2-1])

dp[i] = (1, i) 能搶得最大金額

從左建到右(bottom-up)，保證後面(dp[i])的一定是最大的，因為左邊的 dp[i-1] 或是 dp[i-2] 也已經是最大的