class Solution {
public:
int dp[105];
//dp[i]表示偷取前i个房间获取的最大值
int rob(vector<int>& nums) {
// // dp[i][0];不偷取第i间房,偷取前i-1间房的最大值
// //dp[i][1];偷取第i间房,偷取前i间房的最大值
// memset(dp,0,sizeof(dp));
// dp[0][0]=0;
// dp[0][1]=nums[0];
// for(int i=1;i<nums.size();i++){
// dp[i][1]=max(dp[i-1][0]+nums[i],dp[i][1]);
// dp[i][0]=max(dp[i][0],max(dp[i-1][0],dp[i-1][1]));
// }
// int n=nums.size()-1;
// return max(dp[n][0],dp[n][1]);
memset(dp,0,sizeof(dp));
if(nums.size()<=1) return nums[0];
dp[0]=nums[0];
dp[1]=max(nums[0],nums[1]);
for(int i=2;i<nums.size();i++)
{
dp[i]=max(dp[i-2]+nums[i],dp[i-1]);
}
int n=nums.size()-1;
return dp[n];
}
};
class Solution {
public:
int dp[105];
int rob(vector<int>& nums) {
//考虑0——n-2
memset(dp,0,sizeof(dp));
int n=nums.size();
if(n<=1)
{
return nums[0];
}
dp[0]=nums[0];
dp[1]=nums[0];
for(int i=2;i<n;i++)
{
if(i!=n-1)
{
dp[i]=max(dp[i-1],dp[i-2]+nums[i]);
}
else{
dp[i]=max(dp[i-1],dp[i-2]);
}
}
int res1=dp[n-1];
memset(dp,0,sizeof(dp));
//考虑1——n-1
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]);
}
int res=max(res1,dp[n-1]);
return res;
}
};
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> dfs(TreeNode* root)
{
vector<int>res;
vector<int>s1(2,0);
vector<int>s2(2,0);
//val表示偷根节点
int val=root->val;
//val0表示不偷根节点
int val0=0;
if(root->left!=NULL)
{
s1=dfs(root->left);
val0+=max(s1[0],s1[1]);
val+=s1[1];
}
if(root->right!=NULL)
{
s2=dfs(root->right);
val0+=max(s2[0],s2[1]);
val+=s2[1];
}
res.push_back(val);
res.push_back(val0);
return res;
}
int rob(TreeNode* root) {
vector<int>res;
res= dfs(root);
return max(res[0],res[1]);
}
};
文章来源:https://www.toymoban.com/news/detail-608818.html
文章来源地址https://www.toymoban.com/news/detail-608818.html
class Solution {
public:
int dp[100005];
int minCapability(vector<int>& nums, int k) {
int right=*max_element(nums.begin(),nums.end());
if(nums.size()==1)
{
return nums[0];
}
int left=0;
while(left+1<right)
{
int mid=(left+right)/2;
memset(dp,0,sizeof(dp));
//dp[i]表示前i个房间窃取最大金额为mid的最大房间数
if(nums[0]>mid)
{
dp[0]=0;
}
else{
dp[0]=1;
}
if(nums[1]<=mid && dp[0]==0)
{
dp[1]=1;
}
else{
dp[1]=dp[0];
}
for(int i=2;i<nums.size();i++)
{
if(nums[i]>mid)
{
dp[i]=max(dp[i-1],dp[i-2]);
}
else{
dp[i]=max(dp[i-2]+1,dp[i-1]);
}
}
// int x0=0;//
// int x1=0;//前i位取得的最大值
// for(int i=0;i<nums.size();i++)
// {
// if(nums[i]>mid) x0=x1;
// else{
// int t=x1;
// x1=max(x0+1,t);
// x0=t;
// }
// }
int x1=dp[nums.size()-1];
if(x1>=k)
{
right=mid;
}
else{
left=mid;
}
}
return right;
// = *max_element(nums.begin(), nums.end());
}
};
到了这里,关于打家劫舍系列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!