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

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int robFunc(vector<int>& nums,int start,int end) {
        // int n=nums.size();
        int n =end+1;
        vector<int> dp(n+2,0);
        for(int i=start;i<=end;i++) {
            dp[i+2] = max(dp[i+1],dp[i]+nums[i]);
        }
        return dp[end+2];
    }
    int rob(vector<int>& nums) {
        // write code here
        int n = nums.size();
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        return max(robFunc(nums,0,n-2),robFunc(nums,1,n-1));
    }
};


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

// dp[i+2] = max(dp[i+1],dp[i]+nums[i]);
// return dp[n+1];