论坛开源网站源码,十堰网站建设u2028,住房和城乡建设厅官网证书查询,承德平台文章目录 爬楼梯题意#xff1a;解#xff1a;代码#xff1a; 买卖股票的最佳时机题意#xff1a;解#xff1a;代码#xff1a; 最大子序和题意#xff1a;解#xff1a;代码#xff1a; 打家劫舍题意#xff1a;解#xff1a;代码#xff1a; 爬楼梯
题意… 文章目录 爬楼梯题意解代码 买卖股票的最佳时机题意解代码 最大子序和题意解代码 打家劫舍题意解代码 爬楼梯
题意
从0开始每次1或者2求和为n有多少种可能
解
DP[i]表示到达i能有几种可能
初始状态DP[0]1
递推公式DP[i]DP[i-1]DP[i-2]
因为每次只能1或2所以而状态i-1一定不会影响改变i-2所以正向遍历即可i-2会改变i-1
代码
#includeiostream
#includecstring
using namespace std;
constexpr int N50;
int climbStairs(int n)
{int dp[N];memset(dp,0,sizeof dp);dp[0]1;for(int i0;in;i){dp[i1]dp[i];dp[i2]dp[i];}return dp[n];
}
int main()
{int ans;cinans;ansclimbStairs(ans);coutansendl;
}买卖股票的最佳时机
题意
预知股票价格求一次买入一次卖出能赚的最大金额
解
DP[i]表示第i天前的最低价格
对于第Day天的价格我们要找Day之前最便宜的股票买所以递推式DP[day]min{ Day[0,Day) }
而初始状态第一天之前的价格我们设置成prices[0]即可因为这时候是不赚钱甚至亏钱的保持答案0
那么对于每一天day我们先用今天的价格prices[day]-DP[day-1]获取今天的最高利润然后DP[day]min(prices[day],DP[day-1])更新这一天之前包含的最低价格
由于是一次买入一次卖出所以取最高值并且DP[i]只和DP[i-1]有关而这两者都是基于prices[i]计算/更新
所以用一个变量aftre充当DP[i-1]即可
代码
#includebits/stdc.h
using namespace std;
int maxProfit(vectorint prices)
{int lgprices.size();int afterINT_MAX,ans0;for(auto price:prices){ansmax(ans,price-after);aftermin(after,price);}return ans;
}
int main()
{vectorint prices;int temp;while(cintemp){prices.push_back(temp); }int ansmaxProfit(prices);coutansendl;return 0;
}最大子序和
题意
如题。子数组 是数组中的一个连续部分。
解
主要说一下分治法
思路就是一个区间[l,r]内的最大子数组要么处于[l,mid]要么处于[mid1,r]或者处于[l,r]虽然很像废话但是对计算机来说不一样由于要找子数组所以要保持连续性所以当这个区间内的最大子数组在[l,r]情况下一定是包含[l,mid]的右边和[mid1,r]的左边
那么对于一个区间我们维护它的左起最大子数组、右起最大子数组还有无条件子数组以及区间和
分别有什么作用呢对于最小子区间[t,t]这四个数值都是nums[t]
而对于一个父区间它的左起子数组 是max [l,mid]-left ,[mid1,r]-left[l,mid]-sum为了保持连续性只有两种可能要么是左子区间的 左起最大子数组要么是整个左子区间加上右子区间的 左起最大子数组
对于右起最大子数组也是一样的保留右起的连续性
还有一种无条件子数组指的是不一定包含左起点或者右起点的最大子数组由于这可能是答案的一部分所以要对它进行保留和计算计算方式是左子区间的右连上右子区间的左和两个子区间的无条件子数组中取最大值
代码
#includebits/stdc.h
using namespace std;
struct ITEM
{int l,r,m,sum;
};
ITEM query(int l,int r,vectorint nums)
{//coutl:lrrendl;if(lr) return {nums[l],nums[l],nums[l],nums[l]};int mid(lr)1;ITEM item1query(l,mid,nums);ITEM item2query(mid1,r,nums);ITEM ret;ret.lmax(item1.l,item1.sumitem2.l);ret.rmax(item2.r,item2.sumitem1.r);ret.mmax(item2.litem1.r,max(item1.m,item2.m));ret.sumitem1.sumitem2.sum;return ret;
}
int maxSubArray(vectorint nums)//分治法
{int lgnums.size();ITEM retquery(0,lg-1,nums);int ansmax(ret.l,max(ret.r,ret.m));return ans;
}
/*
int maxSubArray(vectorint nums)//遍历法On
{int lgnums.size(),temp0,ansnums[0];for(auto num:nums){tempnum;ansmax(ans,temp);if(temp0) temp0;}return ans;
}*/
int main()
{vectorint nums;int num;while(cinnum) nums.push_back(num);int ansmaxSubArray(nums);coutansendl;return 0;
}打家劫舍
题意
一个非负整数数组从中选择数字字求最大和要求不能选择连续的数字
解
先将问题想的复杂一点DP[0][i]表示第i个数字不选择时区间[0,i]的最大和DP[1][i]表示选择第i个数字这样可轻松推出dp[0][i]max(dp[0][i-1],dp[1][i-1])和dp[1][i]max(nums[i]dp[0][i-1],dp[0][i-1])
但是我们再想一想DP[i]表示第i个数字不管选不选时区间[0,i]的最大和那么由于不知道i是否被选上所以我们的递推式只能变成DP[i]max(DP[i-1],DP[i-2]nums[i])这样是否合理呢
是合理的因为DP[i]不管选没选择这个递推式都不会选择连续的数字只要初始状态合理就行初始状态设置DP[0]nums[0] DP[1]max(nums[0],nums[1])从第一步DP[2]的计算我们就可以看出无论如何我们都不会计算DP[2]包含nums[1]nums[2]同时由于这个递推式只需要三个变量所以可以用滚动变量解决
代码
#includebits/stdc.h
using namespace std;
int rob(vectorint nums)//J2
{int lgnums.size();if(lg1) return nums[0];int temp1nums[0],temp2max(nums[0],nums[1]);for(int i2;ilg;i){int temptemp2;temp2max(temp2,temp1nums[i]);temp1temp;}return temp2;
}
/*
int rob(vectorint nums)//J1
{int lgnums.size();vectorvectorintdp(2,vectorint(lg));dp[1][0]nums[0];for(int i1;ilg;i){dp[0][i]max(dp[0][i-1],dp[1][i-1]);dp[1][i]max(nums[i]dp[0][i-1],dp[0][i-1]);}return max(dp[0][lg-1],dp[1][lg-1]);
}*/
int main()
{vectorint nums;int num;while(cinnum) nums.push_back(num);int ansrob(nums);coutansendl;return 0;
}
