打家劫舍
题目链接: https://leetcode.cn/problems/house-robber/
解题思路:
报警条件,连续偷了两间房
设定一维dp数组,dp[i]表示到了第i间房偷窃到的最大金额,不一定偷了第i间房
状态转移方程:dp[i]=max(dp[i-2]+nums[i],dp[i-1])
dp[i-2]+nums[i]表示不偷上一家获取到的最大金额
dp[i-1]表示当前房屋不偷获取的最大金额
dp[0]=0表示没有偷,dp[1]表示偷了第一家房子也就是nums[0]
复杂度分析
时间复杂度: 时间复杂度是
空间复杂度: 空间复杂度是
最后更新于