leetcode-213-线性DP-打家劫舍II

发表于 | 分类于

题目

1.png

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 动态规划
class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if(n == 0) return 0;
        if(n == 1) return nums[0];
        // 首间房选或不选
        return max(helper(nums, 0, n-2), helper(nums,1,n-1));
    }

    int helper(vector<int> &nums, int start, int end){
        int memo_i_1 = 0, memo_i_2 = 0;
        int memo_i = 0;
        for(int i = end; i >= start; --i){
            memo_i = max(nums[i] + memo_i_2, memo_i_1);
            memo_i_2 = memo_i_1;
            memo_i_1 = memo_i;
        }
        return memo_i;
    }
};

参考

打家劫舍