LeetCode 198. House Robber

House Robber :

你是一名專業的強盜，計劃搶劫沿街的房屋。 每棟房子都藏有一定數量的金錢，唯一阻止你搶劫的限制是相鄰的房子都連接了安全系統，如果在同一晚兩間相鄰的房子被闖入，它會自動聯繫警察。
給定一個代表每所房子金額的非負整數列表，確定你今晚可以在不報警的情況下搶劫的最大金額。
每個房間裡有些價值的物品，不能偷連續的房間，那麼求最多能偷多少物品？

Python

解法 :

偷第i間就不能偷第i-1間，所以rob[i]=nums[i] + rob[i-2](第i-2間的值加上偷了第i間的值)

不偷第i間，則rob[i] = rob[i-1]，因為沒偷第i間

兩個比較選最大的 : rob[i] = max(nums[i] + rob[i-2], rob[i-1])

class Solution:
    def rob(self, nums: List[int]) -> int:
        l = len(nums)
        if l == 0:
            return 0
        if l == 1:
            return nums[0]
        rob = [0] * l
        rob[0] = nums[0]                #第一間
        rob[1] = max(nums[0], nums[1])  #兩間選一間偷
        
        for i in range(2, l):
            rob[i] = max(nums[i] + rob[i-2], rob[i-1])
            
        return rob[-1]

C++

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return nums[0];
        } else if (n == 2) {
            return max(nums[0], nums[1]);
        }
        
        vector<int> dp(n);
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        for (int i = 2; i < n; i++) {
            dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
        }
        
        return dp[n-1];
    }
};