题解 | #打家劫舍(二)#
打家劫舍(二)
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]);
}
这样去这两者情况的最大值即可。
这个问题是对初始状态分了两种情况，并对最后的数组进行限制。
投递小米集团等公司10个岗位 >
