198. 打家劫舍

发表于 2026-01-03 分类于力扣阅读次数： Waline：本文字数： 514 阅读时长 ≈ 2 分钟

考点

线性DP

思路

一、问题概述

给定一个长度为 \(n\) 的数组 \[ \texttt{nums} = [a_1, a_2, \dots, a_n] \] 其中 \(a_i\) 表示第 \(i\) 间房屋中存放的现金数量。

由于相邻的房屋安装了防盗系统，不能同时抢劫相邻的两间房屋。目标是在不触发警报的前提下，获得可抢劫的最大总金额。

二、动态规划建模思路

该问题具有明显的最优子结构特征，适合使用动态规划求解。

1. 状态定义

定义一维状态数组： \[ f[i] \] 表示在只考虑前 \(i\) 间房屋（第 \(1 \sim i\) 间）时，能够获得的最大金额。

2. 初始值（边界条件）

不考虑任何房屋时：

\[ f[0] = 0 \]

只考虑第一间房屋时：

\[ f[1] = a_1 \]

这两个初始状态为后续递推提供了合法起点。

3. 状态转移方程

对于第 \(i\) 间房屋（\(i \ge 2\)），存在两种选择：

不抢第 \(i\) 间房屋 收益为： \[ f[i-1] \]
抢第 \(i\) 间房屋 由于不能抢相邻房屋，上一间可抢的是第 \(i-2\) 间： \[ f[i-2] + a_i \]

因此状态转移方程为： \[ f[i] = \max \left( f[i-1],\ f[i-2] + a_i \right) \]

4. 结果定义（答案）

在考虑完全部 \(n\) 间房屋后，最终答案为： \[ \boxed{f[n]} \]

三、算法复杂度分析

时间复杂度： \[ O(n) \] 只需一次线性遍历。
空间复杂度： \[ O(n) \] 使用一维 DP 数组保存状态（可进一步优化为 \(O(1)\)，但此处保持清晰性）。

四、实现要点说明

DP 数组下标采用“房屋数量”语义，避免偏移混乱。
使用 nums[i-1] 与 f[i] 对齐，逻辑清晰。
在循环中同步维护当前最大值，最终返回结果。

五、AC代码

class Solution {
public:
    static const int maxn = 1e2 + 5;
    int rob(vector<int>& nums) {
        int f[maxn], res = nums[0];
        f[0] = 0, f[1] = nums[0];
        for (int i = 2; i <= nums.size(); ++i) {
            f[i] = max(f[i - 1], f[i - 2] + nums[i - 1]);
            res = max(res, f[i]);
        }
        return res;
    }
};

0%