上海集酷网站,山东桓台建设招投标网站,app开发公司怎么选,漳州建设局网站首页链接#xff1a;
213. 打家劫舍 II
题意
n个数字围成一圈#xff0c;禁止取相邻#xff0c;求能取到的最大值
解#xff1a;
经典DP特判/一丢丢思维
可以开个bool判断第一个取没取#xff0c;然后判断最后一个#xff0c;同样#xff0c;再倒着做一遍即可
思维
213. 打家劫舍 II
题意
n个数字围成一圈禁止取相邻求能取到的最大值
解
经典DP特判/一丢丢思维
可以开个bool判断第一个取没取然后判断最后一个同样再倒着做一遍即可
思维把0到lg-2 和 1到lg-1各做一遍即可
实际代码
#includebits/stdc.h
using namespace std;
int rob(vectorint nums)
{int lgnums.size();vectorintnums1(lg),nums2(lg);if(lg1) return nums[0];if(lg2) return max(nums[0],nums[1]);nums1[0]nums[0];nums1[1]max(nums[0],nums[1]);for(int i2;ilg-1;i){nums1[i]max(nums1[i-1],nums1[i-2]nums[i]);}nums2[1]nums[1];nums2[2]max(nums[1],nums[2]);for(int i3;ilg;i){nums2[i]max(nums2[i-1],nums2[i-2]nums[i]);}return max(nums1[lg-2],nums2[lg-1]);
}限制
1 nums.length 1000 nums[i] 1000