day12 打家劫舍

真的忙起来了，上次岛屿数量的并查集和 bfs 还没细细咀嚼呢。
打算暂时改为两天一题，之后尽可能补上。

读题

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

又是一个实际情境的题，需要从中抽象出实际的题目。
也就是给定一个 nums 数组，选择一些元素，使之求和最大。这些元素不能相邻。

思路

当然第一反应还是暴力遍历，在“不能相邻”的约束下列举每一种情况，记录求和最大值。
应该是所谓的贪心算法，令求和最大。
如果是暴力遍历，那么基础情况应该是先从第一个元素开始，一个挨一个搜索过去，每个元素选取的都是间隔为一的元素，求和；然后从最后一个元素开始，再尝试间隔不为 1 的元素。
仔细想想，实则不是无穷情况，因为财产数量非负，所以元素越多越有利。那么只有情况：

  • 间隔为 1
  • 间隔为 2

因为如果间隔大于等于 3，那么就可以插入元素，而插入了元素总是比不插入求和更大。
考虑通过树来表示，二叉树，一边是间隔为 1，另一边是间隔为 2，这样问题就是求哪个分支求的和最大，因此可以先构建，后遍历求和。
思路是：

  1. 通过递归构建树，使用 fun 函数，fun 接受节点的指针 node 和数组的指针 p_num：
    1. 将 node->val 设置为 *(p_num)
    2. 如果距离为一的元素存在，fun(node->left, p_num+2)
      1. 否则左子树节点设置为 nullptr
    3. 如果距离为二的元素存在，fun(node->right, p_num+3)
      1. 否则右子树节点设置为 nullptr
  2. 搜索，求和，仍然是使用递归，fun_sum 方法，接受节点的 node，数字当前和 curr_sum
    1. 如果 node 为 nullptr，返回
    2. 将 curr_sum 加 node->val
    3. 如果 max_sum 小于 curr_sum，更新 max_sum（或者当本节点没有子节点才更新，可以节省计算开销）
    4. 有 fun_sum(node->left, curr_sum)
    5. 有 fun_sum(node->right, curr_sum)

于是有代码：

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
class Solution {
public:
    int* p_end=nullptr;
    int max_sum=0;
    struct TreeNode {
        int val;
        TreeNode* left;
        TreeNode* right;
        TreeNode() : val(0), left(nullptr), right(nullptr) {}
        TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
        TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
    };
    void fun(TreeNode* node, int* p_num){
        node->val = *(p_num);
        if(p_num+2<p_end){
            node->left=new TreeNode(*(p_num+2));
            fun(node->left, p_num+2);
        }else node->left=nullptr;
        if(p_num+3<p_end){
            node->right=new TreeNode(*(p_num+3));
            fun(node->right, p_num+3);
        }else node->right=nullptr;
        return;
    }
    void fun_sum(TreeNode* node, int curr_sum){
        if(node==nullptr) return;
        curr_sum+=node->val;
        if(node->left==nullptr&&node->right==nullptr){
            if(max_sum<curr_sum){
                max_sum=curr_sum;
            }
            return;
        }
        if(node->left!=nullptr)fun_sum(node->left, curr_sum);
        if(node->right!=nullptr)fun_sum(node->right, curr_sum);
        return;
    }
    int rob(vector<int>& nums) {
        int length_nums = nums.size();
        p_end = &nums[0]+length_nums;
        max_sum=0;
        TreeNode root(nums[0]);
        fun(&root, &nums[0]);
        fun_sum(&root, 0);
        return max_sum;
    }
};

一开始运行结果是错误的，检查一下发现是+2 和+3 写成了+1 和+2。修改之后跑测试是对的，遂提交。

错误

在测试例 [1,2] 错了，因为我默认是从 0 开始构建树，没有意识到存在这种情况。
于是考虑构建两棵树，遍历两次，得到 max_sum，这样对于代码的修改最小，不过有可能超时和爆空间。

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* p_end=nullptr;
    int max_sum=0;
    struct TreeNode {
        int val;
        TreeNode* left;
        TreeNode* right;
        TreeNode() : val(0), left(nullptr), right(nullptr) {}
        TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
        TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
    };
    void fun(TreeNode* node, int* p_num){
        node->val = *(p_num);
        if(p_num+2<p_end){
            node->left=new TreeNode(*(p_num+2));
            fun(node->left, p_num+2);
        }else node->left=nullptr;
        if(p_num+3<p_end){
            node->right=new TreeNode(*(p_num+3));
            fun(node->right, p_num+3);
        }else node->right=nullptr;
        return;
    }
    void fun_sum(TreeNode* node, int curr_sum){
        if(node==nullptr) return;
        curr_sum+=node->val;
        if(node->left==nullptr&&node->right==nullptr){
            if(max_sum<curr_sum){
                max_sum=curr_sum;
            }
            return;
        }
        if(node->left!=nullptr)fun_sum(node->left, curr_sum);
        if(node->right!=nullptr)fun_sum(node->right, curr_sum);
        return;
    }
    int rob(vector<int>& nums) {
        int length_nums = nums.size();
        p_end = &nums[0]+length_nums;
        max_sum=0;
        TreeNode root0(nums[0]);
        TreeNode root1(nums[1]);
        fun(&root0, &nums[0]);
        fun_sum(&root0, 0);
        fun(&root1, &nums[1]);
        fun_sum(&root1, 0);
        return max_sum;
    }
};

提交，然后 heap-buffer-overflow 了。果然。

或许不应该或者说不需要构建实际的二叉树，而是递归即可，因为不需要保存数据，而且计算求和的过程应该是可以和所谓创建二叉树合并的。
那么，我需要首先合并求和和创建二叉树的过程，然后将二叉树抛弃。
或者，考虑改变分支？
目前的分支是：选择间隔 1 和间隔 2，或许可以改成：选择当前节点 和 跳过当前节点？这样的区别在于：1. 传递的指针是下一节点还是下下节点？2. 传递的数字要不要累加当前节点的 val？
如果不修改，那么就是保留 fun_sum，但是接收 int* p_num, int curr_sum，代码

1


如果修改的话就是：
1
2
3
4
5
6
7
8
9
10
11
void fun_sum(int* p_num, int curr_sum){
    if (p_num >= p_end) {
        if (curr_sum > max_sum) {
            max_sum = curr_sum;
        }
        return;
    }
    fun_sum(p_num+1, curr_sum);
    fun_sum(p_num+2, curr_sum+*(p_num));
    return;
}

提交，然后没有错，但超时了。是复杂度太高了？还是说代码有错误，会陷入死循环？
用官方工具分析了一下，说是 O(2^n) 复杂度。难怪。
有没有什么方法可以减少复杂度？
或许我可以改变搜索方向，从上而下搜索时，记录每个 节点 的当前求和？
但是那样会改变整个的思路吧？
呃，应该不用，也可以像现在这样。

官方题解

放弃思考了，直接看题解。

方法一：动态规划

哎我靠是动态规划。
官方题解言：

  • 如果只有两个节点，选择较高的一个。
  • 如果大于两个，先考虑往前的情况：对于第 n 个节点：
    • 如果选择了，则不能选择第 n-1 个。
      • 那么到此为止，总数额 sum[n] 是 sum[n-2] 加当前节点的值。
    • 如果不选择，则可以选择第 n-1 个。
      • 那么到此为止，总数额 sum[n] 是 sum[n-1]。
  • 于是建立起了全局状态与当前的关系，状态转移方程，有点类似数学归纳法，确定初始条件和递推条件，就能得到结论成立。

特例是：

  1. 只有一间房屋
  2. 只有两间房屋

在大于两间房屋时，上述关系成立。最终的答案即为 dp[length_nums-1]。
官方代码是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.empty()) {
            return 0;
        }
        int size = nums.size();
        if (size == 1) {
            return nums[0];
        }// 特例排除
        vector<int> dp = vector<int>(size, 0);
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);// 初始条件
        for (int i = 2; i < size; i++) {// 递推
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);// 根据状态转移方程
        }
        return dp[size - 1];
    }
};

很简洁，试着运行了一下，是 0ms 通过。太神奇了。
另外 ，官方题解说：上述方法使用了数组存储结果。考虑到每间房屋的最高总金额只和该房屋的前两间房屋的最高总金额相关，因此可以使用滚动数组，在每个时刻只需要存储前两间房屋的最高总金额。
于是空间复杂度应该会小很多。
有代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.empty()) {
            return 0;
        }
        int size = nums.size();
        if (size == 1) {
            return nums[0];
        }
        int first = nums[0], second = max(nums[0], nums[1]);
        for (int i = 2; i < size; i++) {
            int temp = second;
            second = max(first + nums[i], second);
            first = temp;
        }
        return second;
    }
};

虽然看得懂，但下次遇到需要 dp 的题目真不一定能用起来。如果是高度相似的话才能用起来吧。

没有方法二

果然 dp 的题还是要用 dp 来做。

收获

能想到并写出二叉树代码，还是用了不少脑细胞的；但完全没想到 dp。
动态规划 dp 大概就是类似数学归纳法？有初始，有递推，于是可以递推，得到结果。
在这题里，首先需要处理两个特例作为初始条件，然后推导得到递推关系，然后递推，得到 dp 数组，取最后一个作为结果。
看着好像理解了，但还是那句话，遇到新题目，真不一定能辨别出要 dp。

day12 打家劫舍
http://blog.wspdwzh.space/2025/11/03/day12-打家劫舍/
作者
peter？
发布于
2025年11月3日
许可协议