213. House Robber II

  動規五部曲分別為:

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

2. 確定遞推公式

3. dp數組如何初始化

4. 確定遍歷順序

5. 舉例推導dp數組

(from 代碼隨想錄)

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

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

2. 確定遞推公式

circle 表示不能同時搶劫頭跟尾的房子，所以要不考慮 house 0 ~ house n - 1，要不就是 house 1 ~ house n

所以一樣 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數組

略

class Solution {

public:

    int helper(vector<int>& nums, int start, int end)

    {

        vector<int> dp(end - start + 1, 0);

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

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

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

        return dp.back();

    }

    int rob(vector<int>& nums) {

        if(nums.size() == 1) return nums[0];

        if(nums.size() == 2) return max(nums[0], nums[1]);

        int rob1 = helper(nums, 0, nums.size() - 2);

        int rob2 = helper(nums, 1, nums.size() - 1);

        return max(rob1, rob2);

    }

};