广州安全教育平台app下载_网购哪个网站质量好_成都高薪seo_市场监督管理局电话

打家劫舍I

第一题

题意

一个数组 不能选相邻数字 求能选到的最大总和

思路

dp[i]表示下标[0,i]这些能选的最大数字

Code

#define pii pair<int,int>
#define ar2 array<int,2>
#define ar3 array<int,3>
#define ar4 array<int,4>
#define endl '\n'
void cmax(int &a,int b){a=max(a,b);};
void cmin(int &a,int b){a=min(a,b);};
const int N=2e5+10,MOD=1e9+7,INF=0x3f3f3f3f;const long long LINF=LLONG_MAX;const double eps=1e-6;int dp[410];class Solution {
public:int rob(vector<int>& nums) {if(nums.size()==0) return 0;if(nums.size()==1) return nums[0];memset(dp,0,sizeof dp);dp[0]=nums[0];dp[1]=max(nums[0],nums[1]);for(int i=2;i<nums.size();i++){dp[i]=max(dp[i-1],dp[i-2]+nums[i]);}return dp[nums.size()-1];}
};

第二题

打家劫舍II

题意

比上题多了个限制条件 就是0号位置和n-1号位置也视为相邻

思路

dp状态相同
但要分类讨论
nums[0]要么选 要么不选
导致边界状态不同

Code

#define pii pair<int,int>
#define ar2 array<int,2>
#define ar3 array<int,3>
#define ar4 array<int,4>
#define endl '\n'
void cmax(int &a,int b){a=max(a,b);};
void cmin(int &a,int b){a=min(a,b);};
const int N=2e5+10,MOD=1e9+7,INF=0x3f3f3f3f;const long long LINF=LLONG_MAX;const double eps=1e-6;
int dp[1010];class Solution {
public:int rob(vector<int>& nums) {memset(dp,0,sizeof dp);int n=nums.size();if(n==0) return 0;if(n==1) return nums[0];int ans=0;//不选 0 号dp[0]=0;dp[1]=nums[1];for(int i=2;i<n;i++){dp[i]=max(dp[i-1],dp[i-2]+nums[i]);}ans=dp[n-1];//选 0 号memset(dp,0,sizeof dp);dp[0]=nums[0];dp[1]=max(nums[0],nums[1]);for(int i=2;i<n-1;i++){//遍历到倒数第二个数dp[i]=max(dp[i-1],dp[i-2]+nums[i]);}cmax(ans,dp[n-2]);//dp[n-1]==dp[n-2]因为最后一个数不选return ans;}
};