题解 | 打家劫舍(二)

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> dp(n, vector<int>(2, 0));
        int res = 0;

        if(n>0){
            dp[0][0] = 0;
            dp[0][1] = nums[0];
        }
        if(n>1){
            dp[1][0] = nums[1];
            dp[1][1] = nums[0];
        }
        for(int i=2; i<n; i++){
            dp[i][0] = max(dp[i-1][0], dp[i-2][0]+nums[i]);
            dp[i][1] = max(dp[i-1][1], dp[i-2][1]+nums[i]);
        }

        if(n<=2)
            return max(nums[0], nums[1]);
        else
            return max(dp[n-1][0], dp[n-2][1]);
    }
};

这道题其实就是多了一种状态：即，第0号位是否选？

解：

设dp[i][0]表示“不选第0号位时，偷到第i家最多能赚多少钱；

设dp[i][1]表示“选择第0号位时，偷到第i家最多能赚多少钱；

则有初始条件如下：

if(只有1家):
	只偷这1家;
if(有2家):
	偷钱最多的那一家;
if(>2家):
	dp[0][0]=0;				// 来到第0家：不偷第0家，则收益为0
	dp[0][1]=nums[0];		// 来到第0家：偷第0家，则收益为nums[0]
	dp[1][0]=nums[1];		// 来到第1家：不偷第0家，则可以偷第1家，收益为nums[1]
	dp[1][1]=nums[0];		// 来到第1家：偷第0家，则不能偷第1家，收益维持不变nums[0]
for(int i=2; i<一共几家; i++){
	// 没偷第0家的情况只能在之前也没偷第0家的基础上计算
	dp[i][0] = max(dp[i-1][0], dp[i-2][0]+nums[i];
	// 偷了第0家的情况只能在之前已经偷了第0家的基础上计算
	dp[i][1] = max(dp[i-1][1], dp[i-2][1]+nums[i];
}
// 如果没偷第0家，则计算偷到倒数第2家时的收益，即dp[n-2][0]
// 如果偷了第0家，则计算偷到最后1家时的收益，即dp[n-1][1]
return max(dp[n-2[0], dp[n-1][1]);