原题链接:
https://leetcode.cn/problems/house-robber/description/

解法1

动态规划 

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
/*  
    状态表示 f[i] 表示从前i家偷的最大值  注意这里的i表示 前i 这对后续的状态转移的理解很关键
    状态计算 -> 以最后一家为界:
    偷: f[i] = f[i - 2] + nums[i]  
    根据题目要求则只能从前 i-2 家偷的最大值转移而来 -> f[i - 2] + nums[i] 

    不偷: f[i] = f[i - 1]  则可以直接由上一家转移而来 

    即 f[i] = max(f[i - 1] , f[i - 2] + nums[i]) 
    但这样会产生负数下标 
    注意由于f[i]  可以理解存储的值的方式 那么可以直接把 f[i] 对应的全部 + 2 j 即规避了初始化问题
*/
class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        // 这种情况 不用考虑边界会更加简洁
        int f[n + 2];
        memset(f,0,sizeof f);
        
        for(int i = 0 ; i < n ; i++){
            f[i + 2] = max(f[i + 1],f[i] + nums[i]);
        }

        return f[n + 1];
    }
};

扩展: 环形打家劫舍 leetcode213

原题链接:
https://leetcode.cn/problems/house-robber-ii/description/

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
/*
    动态规划
    相较于198 多了 环形的条件 主要影响头尾的判断 记录房屋为h
    h[0] 选了 则 h[n - 1] 不能选    反之同理    
    而h[1] --- h[n - 2] 的情况是与198 完全相同的
    由于h[0] 与 h[n - 1] 只有两种情况
    那么不妨走两遍 取最大值即为本题答案

    1. 选h[0]时 -> f[0] = nums[0] 此时只用算 2 --- n-2
        注意不是 1 --- n-2 因为根据题目相同要求  0 与 1 也是相邻的所以也是不能选的 所以直接从2开始
    2. 不选h[0] 时 f[0] = 0 此时只用算 1 --- n-1
*/
class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        int f1[n + 2],f2[n + 2];
        memset(f1,0,sizeof f1);
        memset(f2,0,sizeof f2);

        
        // 情况1 
        // f1[0] = nums[0];  注意这样写时没有意义的 因为根据定义nums[0] 是必须要加的
        // 从i = 2 开始其实是算不到f1[0]的 没有意义
        for(int i = 2 ; i < n - 1; i++){
            f1[i + 2] = max(f1[i + 1] , f1[i] + nums[i]);
        }

        // 情况2 
        f2[0] = 0;
        for(int i = 1 ; i < n ; i++){
            f2[i + 2] = max(f2[i + 1], f2[i] + nums[i]);
        }

        return max(f1[n] + nums[0],f2[n + 1]);
    }
};