198. 打家劫舍
一句话套路偷/不偷:max(prev1, prev2+x)
题目描述
你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。
示例 1:
输入:[1,2,3,1] 输出:4 解释:偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。
示例 2:
输入:[2,7,9,3,1] 输出:12 解释:偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。
提示:
1 <= nums.length <= 1000 <= nums[i] <= 400
思路
时间
O(n)空间
O(1)状态
dp[i] = 偷到第 i 间房为止(可以偷 i)的最大金额。
转移
dp[i] = max(dp[i-1], dp[i-2] + nums[i]) —— 要么不偷 i,要么偷 i(则 i-1 必不偷)。
因为只依赖前两项,滚动成两个变量即可 O(1) 空间。
家族
Q213 环形(拆成「不偷首」和「不偷尾」两次线性 DP 取 max)、Q337 树形 DP(每个结点返回「偷/不偷」两个值,见 08 文件的 Q124 思路)。
图解
数组(来自本仓库测试数据,下标从 0 开始)
逐帧动画
1 / 5
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
namespace lc0198 {
class Solution {
public:
int rob(vector<int>& nums) {
int prev2 = 0, prev1 = 0; // dp[i-2], dp[i-1]
for (int x : nums) {
int cur = max(prev1, prev2 + x);
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0198::Solution s;
vector<int> a{1, 2, 3, 1};
CHECK_EQ(s.rob(a), 4); // 1+3
vector<int> b{2, 7, 9, 3, 1};
CHECK_EQ(s.rob(b), 12); // 2+9+1
vector<int> c{2, 1};
CHECK_EQ(s.rob(c), 2);
vector<int> d{5, 1, 1, 5}; // 下标 0 与 3 不相邻,线性版可以同时偷(换成环形 Q213 才互斥)
CHECK_EQ(s.rob(d), 10);
vector<int> e{0};
CHECK_EQ(s.rob(e), 0);