题解 | #打家劫舍(二)#

class Solution {
public:
    int rob(vector<int>& nums) {
        //dp[i]表示长度为i+1的数组，最多能偷取多少钱
        vector<int> dp(nums.size(), 0); 
        //选择偷了第一家
        dp[0] = nums[0]; 
        //最后一家不能偷
        for(int i = 1; i < nums.size(); i++) 
        {
            if(i==1)
                dp[i] = max(dp[i - 1], nums[i]); 
            else
                //对于每家可以选择偷或者不偷
                dp[i] = max(dp[i - 1], nums[i] + dp[i - 2]); 
        }

        //最后一家不能偷
        int res = dp[nums.size() - 2]; 
        //清除dp数组，第二次循环
        dp.clear(); 
        //不偷第一家
        dp[0] = 0; 
        //可以偷最后一家
        for(int i = 1; i < nums.size(); i++)
        {
            if(i==1)
                dp[i] = nums[i];
            else
                //对于每家可以选择偷或者不偷
                dp[i] = max(dp[i - 1], nums[i] + dp[i - 2]); 

        }
            
        //选择最大值
        return max(res, dp[nums.size()-1]); 
    }
};


// #include <vector>
// class Solution {
// public:
//     /**
//      * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//      *
//      * 
//      * @param nums int整型vector 
//      * @return int整型
//      */
//     int rob(vector<int>& nums) {
//         // write code here
//         // 与打家劫舍(一)不同，该题每个房间都可能是第一家被偷的存在
//         int n = nums.size();
//         int ans = 0;

//         if(n==0)
//             return 0;

//         // i 为第一家被偷的房间
//         for(int i=0; i<n; ++i)
//         {
//             vector<int> dp(n-1,0);

//             // 最后一家和第一家是相邻的，所以算了第一家，就不算最后一家了
//             for(int j=i; j-i<n-1; ++j)
//             {
//                 if(j==i)
//                     dp[0] = nums[i];
//                 else if(j==i+1)
//                     dp[1] = max(dp[0],nums[j%n]);
//                 else
//                     dp[j-i] = max(dp[j-i-1],dp[j-i-2]+nums[j%n]);
//             }

//             ans = max(ans,dp[n-2]);
//         }

//         return ans;
//     }
// };