头脑风暴:打家劫舍 2
题目
你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组,计算你 在不触动警报装置的情况下 ,今晚能够偷窃到的最高金额。
示例 1:
复制代码
示例 2:
复制代码
示例 3:
复制代码
解题思路
之前我们已经做过一道打家劫舍的题目了,利用动态规划可以求解,本题与之前的题目唯一的区别在于成环了。
对于数组,成环主要有以下三种情况:
情况一:考虑不包含首尾元素例如,数组 [1,6,1,9,1], 我们考虑的情况就是下标从 1~3 的情况,也就是[6,1,9];
情况二:考虑包含首元素,不包含尾元素例如,数组 [1,6,1,9,1], 我们考虑的情况就是下标从 0~3 的情况,也就是[1,6,1,9];
情况三:考虑包含尾元素,不包含首元素例如,数组 [1,6,1,9,1], 我们考虑的情况就是下标从 1~4 的情况,也就是[6,1,9,1];
由于情况一已经被情况二和三所包含,所以我们在求解的时候,只需要包含后俩种情况即可。
代码实现
复制代码
最后
时间复杂度:O(n),其中 n 是数组长度。
空间复杂度:O(1)。
版权声明: 本文为 InfoQ 作者【HelloWorld杰少】的原创文章。
原文链接:【http://xie.infoq.cn/article/0bf4dbe304b2335137d47bd4f】。文章转载请联系作者。
评论