题解 | #打家劫舍(二)#

打家劫舍(二)

https://www.nowcoder.com/practice/a5c127769dd74a63ada7bff37d9c5815

2022.0818算法第35题打家劫舍(二)
这个没想出来,没成想嗜血要分成两种情况进行打家劫舍(一)的那种解法。
思考的时候想到了将这两者进行区分,还是太受局限了
1、状态矩阵
dp[i]表示前i个房间的最大偷窃金额,
vector<int> dp(nums.size()+1);
2、初始状态
dp[1]=nums[0];
//或者
dp[1]=0;
只有一个房子的时候,不要犹豫,直接偷。
3、状态转移方程
dp[i]=max(dp[i-2]+nums[i-1],dp[i-1]);
这个因为首尾相连,第一个和最后一个不能同时偷,
分成两种情况
1、偷第一家
dp[1]=nums[0];
这样最后一家就能不能偷,直接进行舍弃,循环的时候不要
for(int i=2;i<nums.size();i++){
    dp[i]=max(dp[i-2]+nums[i-1],dp[i-1]);
}
此时没有=号,不会考虑最后一个房子。
2、不偷第一家
dp[1]=0;
这样最后一家也需要考虑
for(int i=2;i<=nums.size();i++){
    dp[i]=max(dp[i-2]+nums[i-1],dp[i-1]);
}
这样去这两者情况的最大值即可。

这个问题是对初始状态分了两种情况,并对最后的数组进行限制。








#算法题#
全部评论

相关推荐

威猛的小饼干正在背八股:挂到根本不想整理
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务