[LeetCode] 198. House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

有一排房子,小偷可以去偷 如果偷了第一間就不能偷第二間(不能偷相鄰的), 請問小偷的最大利益?

號稱最經典 最簡單的 動態規劃題目. 什麼是動態規劃?

 https://www.youtube.com/watch?v=J3oLkc_TEVw

思路: 

定義狀態 -> 轉移方程 -> 計算最優解並存下來 -> 由小到大推導結果

假設一排房子裡面的價值是 [2,1,1,1], 請問小偷的最大利益?

1. 定義狀態

設定 dp[3] 為小偷的最大利益

2.轉移方程

來看 dp[0] 是什麼意思, 如果只有一間房子 [2] 請問小偷的最大利益是多少?

很明顯 如果小偷 不偷那利益就是 0 偷了就是 2 所以當然是偷, 故 dp[0] = house[0]

再看 dp[1] 是什麼意思, 如果有兩間房子 [2,1] 請問小偷的最大利益是多少? 比一下就知道了

dp[1] = max (house[0], house[1])

再看 dp[2] 應該是, 如果有三房子 [2,1,1]  請問小偷的最大利益是多少?

因為題目說不能偷相鄰的 所以只有兩種情況 house[0] + house[2] 或是 house[1]

dp[2] = max( house[2] + house[0], house[1] )

最後推導出, 

dp[n] = max ( house[n]+dp[n-2], house[n-1] )

3.計算最優解並存下來

存下只有一棟房子的最大利益 到 dp[0]

存下只有兩棟房子的最大利益 到 dp[1]

4.由小到大推導結果

按照公式推導 dp[n]

        for i in range( 2, len(nums) ):
            dp.append( max(nums[i] + dp[i-2] , dp[i-1] ) )
        return dp[-1]