213. 打家劫舍 II

思路：考慮三種情況注釋代碼中

class Solution { public:int rob(vector<int>& nums) {if(nums.empty()) return 0;if(nums.size()==1) return nums[0];//考慮首端，不考慮尾端int value1 = robrange(nums,0,nums.size()-2);//考慮尾端，不考慮首端int value2 = robrange(nums,1,nums.size()-1);return max(value1,value2);}//考慮以下三種情況//1:不考慮首尾的情況//2:考慮首端情況//3:考慮尾端情況//由于情況1包含在情況2，3中，所以只要考慮后面兩個即可int robrange(vector<int>& nums,int start,int end){if (end == start) return nums[start];vector<int> dp(nums.size(),0); //第i個房間最高金額是dp[i]dp[start] = nums[start];dp[start+1] = max(nums[start],nums[start+1]);for(int i=start+2;i<=end;i++){dp[i] = max(nums[i]+dp[i-2],dp[i-1]);}return dp[end];} };

總結

以上是生活随笔為你收集整理的LeetCode-动态规划-213. 打家劫舍 II的全部內容，希望文章能夠幫你解決所遇到的問題。

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