198. House Robber

 動規五部曲分別為:

1. 確定dp數組(dp table)以及下標的含義

2. 確定遞推公式

3. dp數組如何初始化

4. 確定遍歷順序

5. 舉例推導dp數組

(from 代碼隨想錄)

1. 確定dp數組(dp table)以及下標的含義

dp[i] 代表考慮 0 ~ i house 所能搶劫到的最大 $$

2. 確定遞推公式

分成要搶 house i 或不搶兩個 case

dp[i] = max(dp[i-2] + nums[i], dp[i-1]);

3. dp數組如何初始化

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

其餘為 0

4. 確定遍歷順序

由左到右

5. 舉例推導dp數組

Input: nums = [1,2,3,1]

=> [1, 2, 4, 4]

class Solution {

public:

    int rob(vector<int>& nums) {

        if(nums.size() < 2) return nums[0];

        vector<int> dp(nums.size(), 0);

        dp[0] = nums[0], dp[1] = max(nums[0], nums[1]);

        for(int i=2; i<nums.size(); i++)

            dp[i] = max(dp[i-2] + nums[i], dp[i-1]);

        return dp.back();

    }

};