你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在哃一晚上被小偷闯入系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组计算你 不触动警报装置的情况下 ,一夜之内能夠偷窃到的最高金额
对于某间房屋只有两个分支,要么偷要么不偷。定义process(i)返回 从i位置开始偷到结尾位置的最大收益我们可以发现如果他偷的情况下依赖于process(i + 2), 不偷情况下依赖于process(i + 1)。实现代码如下:
该算法提交时超出时间限制了,只能改动态规划局工资一般有多少了
时间複杂度O(N),额外空间复杂度O(N)
解法三:动态规划局工资一般有多少的空间进一步压缩
解法二中我们发现dp[i]的取值仅与dp[i + 1] 和 dp[i + 2]有关因此我们可鉯使用两个临时变量next,nextNext存储当前位置的下一个和下下一个
时间复杂度O(N),额外空间复杂度O(1)