LeetCode198——house robber（不懂dp）

　　这题，是不能连续抢两间相邻的店铺。我不知道是不是一个环，姑且算作不是一个环。

　　如果你已经来到了第n间店铺，那么你有两个选择。

　　1.抢：sum［n］ ＝ sum［n － 2］ ＋n.value  。第n － 1不能抢

　　2.不抢：你的总收益来到前面一家店的收益总和sum［n］ ＝sum［n － 1］。

　　所以！我们只需要比较这两者的大小，就可以得出我们的最佳选择是什么了。

　　为了方便理解，假设a，b，c三间店铺。你来到了c店铺，c店铺不抢的话，你应该在a，b店铺中找一个最大的来抢。c抢的话，那么就是a ＋ c两者之和。需要比较a，b中大的和a ＋ c的和谁大。

　　同理，如果将通常情况分为n－2，n－1，n三个店铺。那么你来到n你抢n则是n－2 ＋ n，不抢的话则应该在n－2和n－1两种解决方式之中找寻最大的方式来抢。

class Solution {
public:int rob(vector<int>& nums) {if(nums.size() == 0){return 0;}else if(nums.size() == 1){return nums[0];}else if(nums.size() == 2){return max(nums[0],nums[1]);}int n1 = nums[0];int n2 = max(nums[0],nums[1]);for(int i = 2;i != nums.size();++ i){int n = n1 + nums[i];//第一次是第三间铺子int n3 = n > n2 ? n : n2;//第三间铺子抢不抢？抢就是n，不抢就是n2；n1 = n2;n2 = n3;}return max(n1,n2);}
};

转载于:https://www.cnblogs.com/thewaytomakemiracle/p/5045776.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！