House Robber

198. 打家劫舍

分析

定义状态：
- f[i]：表示偷取第 i 个房屋的最高金额
- g[i]：表示不偷取第 i 个房屋的最高金额
状态转移方程：
- 若偷第 i 个房屋：f[i] = g[i - 1] + nums[i - 1]，即前一个房屋没有被偷，当前房屋可以偷取，累加其金额。
- 若不偷第 i 个房屋：g[i] = max(f[i - 1], g[i - 1])，即第 i 个房屋不被偷，其最优结果取决于前一个房屋偷或不偷的最大值
初始化：
- f[0] = 0（没有房屋可偷）
- g[0] = 0 （没有房屋可偷）
结果：
- 最终的最大金额为：max(f[n], g[n])

时间复杂度

遍历一次数组，时间复杂度为 O(n)

空间复杂度

使用两个长度为 n + 1 的数组，空间复杂度为 O(n)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution
{
public:
    int rob(vector<int>& nums)
    {
        int n = nums.size();
        std::vector<int> f(n + 1), g(n + 1);  // 定义偷和不偷的状态数组

        for (int i = 1; i <= n; ++ i)
        {
            f[i] = g[i - 1] + nums[i - 1];  // 偷当前房屋
            g[i] = std::max(f[i - 1], g[i - 1]);  // 不偷当前房屋
        }

        return std::max(f[n], g[n]);  // 返回最大值
    }
};