题解 | #打家劫舍(一)#
2022.0818算法第34题打家劫舍(一)
动态规划能求解，自己能想出来，应该不算难。
1、状态方程
dp[i]表示第i个房间的最大偷窃金额，就这一个数组，也没啥其他的选择
vector<int> dp(nums.size());2、初始状态
取前两个值
dp[0]=nums[0];
if(nums[0]<nums[1]){
dp[1]=nums[1];
}
else
dp[1]=dp[0];
3、状态转移方程
动态规划是从底层往上进行的，
可以先写出前面的规律，这样就好理解了
dp[0]=nums[0]刚开始只有一种选择
dp[1]=max(nums[0],nums[1])这时候有两种选择，去两者的最大值
dp[2],这时候也是有两种选择，要么把nums[1]跳过去，要么不跳nums[1]，那么只需要去这两者的最大值即可。dp[2]=max(dp[0]+nums[2],dp[1])
其中dp[0]+nums[2]是跳过nums[1]的情况；dp[1]是不跳nums[1]的情况。
dp[3]=max(dp[1]+nums[3],dp[2])，其中dp[1]+nums[3]是跳过nums[2]的情况；dp[1]是不跳nums[2]的情况。
.。。。。。
得到状态转移方程为
dp[i]=max(dp[i-2]+nums[i],dp[i-1]);最后返回最后的值即可
return dp[nums.size()-1];
海康威视工作强度 82人发布
投递百度等公司10个岗位 >