leetcode198：打家劫舍

题目链接

leetcode

题目描述

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

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/*
    状态表示：
        f[i] 表示前 i 个房屋取到的最高金额
    状态计算：
        根据最后一个点进行划分。
        不选第 i 点，转化为 [...i-1] 取到的最高金额
            f[i] = max(f[i], f[i-1])
        选择第 i 个点，因为不能选择相邻的点，从 [...i-2] 中选
            f[i] = max(f[i], f[i-2] + nums[i])
    边界条件：
        f[0] = nums[0]
        f[1] = max(f[0], nums[1])
    最终答案：f[n−1]

    时间复杂度：O(n)
        其中 n 是数组长度，对数组遍历一次。
    空间复杂度：O(n)
*/
class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) {
            return nums[0];
        }

        vector<int> f(n, 0);
        // 初始化
        f[0] = nums[0];
        f[1] = max(nums[0], nums[1]);

        // 状态计算
        for (int i = 2; i < n; i++) {
            f[i] = max(f[i-1], f[i-2] + nums[i]);
        }

        return f[n-1];
    }
};

/*
    优化空间

    时间复杂度：O(n)
    空间复杂度：O(1)
        存储前两个房屋的最高金额，不需要存储整个数组的结果。
*/
class Solution_3 {
public:
    int rob(vector<int>& nums) {
        int start = 0, end = nums.size()-1;
        // 初始化
        int prev2 = 0, prev1 = 0, cur = 0;

        // 状态计算
        for (int i = start; i <= end; i++) {
            cur = max(prev2 + nums[i], prev1);
            prev2 = prev1;
            prev1 = cur;
        }

        return cur;
    }
};

// 辅助函数：打印数组
void printArray(const vector<int>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]";
}

int main() {
    Solution solution;
    vector<vector<int>> nums_cases = {
        {1,2,3,1},
        {2,7,9,3,1}
    };

    for (auto& nums : nums_cases) {
        cout << "Input: ";
        printArray(nums);
        cout << endl;
        int result = solution.rob(nums);
        cout << "Output: " << result << endl;
    }

    return 0;
}