leetcode-198-线性DP-打家劫舍

发表于 | 分类于

题目

1.png

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// 递归 + 备忘录
class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.empty()) return 0;
        vector<int> memo(nums.size(), -1);
        return helper(nums, 0, memo);
    }

    // 从索引start开始偷取获得的最大利润
    int helper(vector<int> &nums, int start, vector<int> &memo){
        if(start >= nums.size()) return 0;
        if(memo[start] != -1) return memo[start];

        int res = max(nums[start] + helper(nums, start+2, memo), helper(nums, start+1, memo));
        memo[start] = res;
        return res;
    }
};

// 动态规划

class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.empty()) return 0;
        // memo[i] = x 表示从第i间房子开始抢劫，最大收益为x
        vector<int> memo(nums.size()+2, 0);
        for(int i = nums.size()-1; i >= 0; --i){
            memo[i] = max(nums[i] + memo[i+2], memo[i+1]);
        }
        return memo[0];
    }
};

// 动态规划，优化空间复杂度
class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.empty()) return 0;
        int memo_i_1 = 0, memo_i_2 = 0;
        int memo_i = 0;
        for(int i = nums.size()-1; i >= 0; --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;
    }
};