专业做效果图网站,外贸网页制作公司,快猫,免费的网站推广软件题目#xff1a;198.打家劫舍
怎么确定当前的房间偷还是不偷呢#xff1f;其实和前两个房间有关系的——动态规划
1.dp数组含义#xff1a;考虑下标 i 和 i 之前的房间#xff08;dp[i] 不一定会偷第 i个房间#xff09;,所能偷的最大的金币
2.动态转移方程#xff1a…题目198.打家劫舍
怎么确定当前的房间偷还是不偷呢其实和前两个房间有关系的——动态规划
1.dp数组含义考虑下标 i 和 i 之前的房间dp[i] 不一定会偷第 i个房间,所能偷的最大的金币
2.动态转移方程dp[i] max(dp[i - 2] nums[i], dp[i - 1]) 两种情况①偷第 i 房间也就意味着一定不能头nums[i - 1]dp[i - 2] nums[i] ②不偷第 i 个房间那么最大值来自dp[i - 1]dp[i - 1]
3.初始化递推公式的基础是dp[0] 和 dp[1] dp[0] nums[0]dp[1] max(dp[0]dp[1]) 紧贴公式来考虑怎样来初始化当i 0时第一个房价是一定要偷的当i 1时dp[1]应该为前两个房间所能偷的最大值又因为两个房间不能一起偷所以去前两个房间的最大值作为dp[1]。这样就叫紧贴dp含义来进行初始化
4.遍历顺序从小到大i 从2开始
5.打印dp
代码如下
class Solution {
public:int rob(vectorint nums) {vectorint dp(nums.size(), 0);dp[0] nums[0];dp[1] max(nums[0], nums[1]);for(int i 2; i nums.size(); i){dp[i] max(dp[i - 2] nums[i], dp[i - 1]);}return dp[nums.size() - 1];}
}; 题目213.打家劫舍|| 这道题和198.打家劫舍的区别就在于本题最后一个房屋和第一个房屋紧挨着所有房间围成一个圈。这样的话会带来什么影响呢
思路化环形为线型
在遇到环时可以如此考虑展开呈线型
情况一考虑不包含首尾元素情况二考虑包含首元素不包含尾元素情况三考虑包含尾元素不包含首元素
注意这里是考虑例如情况三虽然是考虑包含尾元素但不一定要选尾部元素 对于情况三取nums[1] 和 nums[3]就是最大的。
而情况二 和 情况三 都包含了情况一了所以只考虑情况二和情况三就可以了。
代码如下
有一些溢出判断是很值得注意的
class Solution {
public:int rob(vectorint nums) {if(nums.size() 0) return 0;if(nums.size() 1) return nums[0];int res1 robRange(nums, 0, nums.size() - 2);int res2 robRange(nums, 1, nums.size() - 1);return max(res1, res2);}int robRange(vectorint nums, int start, int end){if(end start) return nums[start];vectorint dp(nums.size());dp[start] nums[start];dp[start 1] max(nums[start], nums[start 1]);for(int i start 2;i end; i){dp[i] max(dp[i - 2] nums[i], dp[i - 1]);}return dp[end];}
}; 题目337.打家劫舍|||
