动态规划-leetcode#213 打家劫环形舍

本文主要是介绍动态规划-leetcode#213 打家劫环形舍，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这题与leetcode#198相似，只是升级为环形房屋，也就是第一个和最后一个也是相邻的。回顾一下简单版解决方案：

class Solution {//leetcode#198代码
public:int rob(vector<int>& nums) {if(nums.empty()) return 0;vector<int> dp(nums.size(),0);dp[0]=nums[0];for(int i=1;i<nums.size();i++){int use_i = i>=2?dp[i-2]+nums[i]:nums[i];int not_i = dp[i-1];dp[i] = max(use_i,not_i);}return dp[nums.size()-1];}
};

环形的屋，也就是说打劫第一家，就不能打劫最后一家，打劫最后一家就不能打劫第一家，因此分两次求最大值，然后整体求最大值。

class Solution {
public:int rob(vector<int>& nums) {if(nums.empty()) return 0;if(nums.size()==1) return nums[0];vector<int> dp(nums.size(),0);dp[0]=nums[0];int res=0;for(int i=1;i<nums.size()-1;i++){int use_i = i>=2?dp[i-2]+nums[i]:nums[i];int no_i = dp[i-1];dp[i] = max(use_i,no_i);}res = dp[nums.size()-2];dp[0]=0;for(int i=1;i<nums.size();i++){int use_i = i>=2?dp[i-2]+nums[i]:nums[i];int no_i = dp[i-1];dp[i] = max(use_i,no_i);}res = max(res,dp[nums.size()-1]);return res;}};

 

这篇关于动态规划-leetcode#213 打家劫环形舍的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---