這題，是不能連續搶兩間相鄰的店鋪。我不知道是不是一個環，姑且算作不是一個環。

　　如果你已經來到了第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

總結

以上是生活随笔為你收集整理的LeetCode198——house robber（不懂dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。