DP-LeetCode-198. 打家劫舍
题目
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/house-robber 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思想
闫氏DP分析
因为相邻两间房不能同时偷，最多只能偷其中的一家。这就提示我们用两种状态表示 f[i]表示偷第i家可以获得的最大值 g[i]表示不偷第i家可以获得的最大价值 (1)第i偷，说明前一家不偷 f[i]状态的更新 f[i] = g[i - 1] + nums[i]; (1)第i不偷，说明当前能偷的最大价值就是前一家偷或者不偷的最大值 g[i]状态的更新 g[i] = max(f[i - 1], g[i - 1]); 结果状态的更新 ans = max(ans, max(f[i], g[i]));
代码
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
vector<int> f(n + 1);//偷
vector<int> g(n + 1);//不偷
int ans = INT_MIN;
for (int i = 1; i <= n; i++) {
f[i] = g[i - 1] + nums[i - 1];
g[i] = max(g[i - 1], f[i - 1]);
ans = max(ans, max(f[i], g[i]));
}
return ans;
}
};
// 空间优化
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
int g = 0;
int f = 0;
int ans = INT_MIN;
for (int i = 1; i <= n; i++) {
int nf = g + nums[i - 1];
int ng = max(f, g);
ans = max(ans, max(nf, ng));
f = nf;
g = ng;
}
return ans;
}
};本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录