动态规划的题，我先用最初级的方式写出来
class Solution { public: int rob(vector<int>& nums) { if(nums.size()==0) { return 0; } int n=nums.size(); if(n==1) { return nums[0]; } //0为偷，1为不偷 //dp[i][n]为最大金钱 //dp[i][0]=dp[i-1][1]+nums[i],dp[i][1]=max(dp[i-1][0],dp[i-1][1]); vector<vector<int>>dp(nums.size(),vector<int>(2,0)); vector<vector<int>>dp2(nums.size(),vector<int>(2,0)); //不选首节点 for(int i=1;i<nums.size();i++) { dp[i][0]=(i-1>=0?dp[i-1][1]:0)+nums[i]; dp[i][1]=(i-1>=0?max(dp[i-1][0],dp[i-1][1]):0); } //不选尾节点 for(int i=0;i<nums.size()-1;i++) { dp2[i][0]=(i-1>=0?dp2[i-1][1]:0)+nums[i]; dp2[i][1]=(i-1>=0?max(dp2[i-1][0],dp2[i-1][1]):0); } return max(max(dp[n-1][0],dp[n-1][1]),max(dp2[n-2][0],dp2[n-2][1])); } };
首尾节点不能同时选也是个比较难处理的点，我在看了别人的答案后写出了以上答案。
如下图，只要考虑情况二和三就好，因为包含了情况一。
方式二:
class Solution { public: int rob(vector<int>& nums) { if(nums.size()==0) { return 0; } int n=nums.size(); if(n==1) { return nums[0]; } //0为偷，1为不偷 //dp[i][n]为最大金钱 //dp[i][0]=dp[i-1][1]+nums[i],dp[i][1]=max(dp[i-1][0],dp[i-1][1]); //优化空间版，只需要记录上一次的偷和不偷就可以了 int i_0=0,i_1=0; //不选首节点 for(int i=1;i<nums.size();i++) { // int tmp_i_1=(i-1>=0?max(i_0,i_1):0); i_0=(i-1>=0?i_1:0)+nums[i]; i_1=tmp_i_1; } //不选尾节点 int j_0=0,j_1=0; for(int i=0;i<nums.size()-1;i++) { int tmp_j_0=(i-1>=0?j_1:0)+nums[i]; j_1=(i-1>=0?max(j_0,j_1):0); j_0=tmp_j_0; } return max(max(i_0,i_1),max(j_0,j_1)); } };