合肥网站建合肥网站建设找蓝领商务建设企业网站公

当前位置： 首页 > news >正文

合肥网站建合肥网站建设找蓝领商务,建设企业网站公,好听的工程公司名字,凡科网和wordpress参考资料#xff1a;代码随想录 (programmercarl.com)一、只能买卖一次题目链接#xff1a;121. 买卖股票的最佳时机 - 力扣#xff08;LeetCode#xff09;算法思想#xff1a;设置两种状态:0表示已持有股票#xff0c;1表示未持有股票1.dp[i][0]表示第i天已持有股票时代码随想录 (programmercarl.com)一、只能买卖一次题目链接121. 买卖股票的最佳时机 - 力扣LeetCode算法思想设置两种状态:0表示已持有股票1表示未持有股票1.dp[i][0]表示第i天已持有股票时获得的最大利润dp[i][1]表示第i天未持有股票时获得的最大利润2.递推式:对于dp[i][0]: 若第i-1天已持有股票则dp[i][0]dp[i-1][0]; 若第i-1天未持有股票则dp[i][0]0-prices[i];综上,dp[i][0]fmax(dp[i-1][0],-prices[i]);对于dp[i][1]: 若第i-1天未持有股票则dp[i][1]dp[i-1][1]; 若第i-1天已持有股票则dp[i][1]dp[i-1][0]prices[i];综上:dp[i][1]fmax(dp[i-1][1],dp[i-1][0]prices[i]);3.初始化:dp[0][0]-prices[0];算法实现int maxProfit(int *prices,int pricesSize){//设置两种状态:0表示已持有股票1表示未持有股票//1.dp[i][0]表示第i天已持有股票时获得的最大利润//dp[i][1]表示第i天未持有股票时获得的最大利润//2.递推式://对于dp[i][0]:// 若第i-1天已持有股票则dp[i][0]dp[i-1][0];// 若第i-1天未持有股票则dp[i][0]0-prices[i];//综上,dp[i][0]fmax(dp[i-1][0],-prices[i]);//对于dp[i][1]:// 若第i-1天未持有股票则dp[i][1]dp[i-1][1];// 若第i-1天已持有股票则dp[i][1]dp[i-1][0]prices[i];//综上:dp[i][1]fmax(dp[i-1][1],dp[i-1][0]prices[i]);//3.初始化://dp[0][0]-prices[0];int dp[pricesSize][2];memset(dp,0,sizeof(dp));dp[0][0]-prices[0];for(int i1;ipricesSize;i){dp[i][0]fmax(dp[i-1][0],-prices[i]);dp[i][1]fmax(dp[i-1][1],dp[i-1][0]prices[i]);}return dp[pricesSize-1][1]; }二、可以买卖多次题目链接122. 买卖股票的最佳时机 II - 力扣LeetCode算法思想设置两种状态:0表示已持有股票1表示未持有股票1.dp[i][0]表示第i天已持有股票时获得的最大利润dp[i][1]表示第i天未持有股票时获得的最大利润2.递推式:对于dp[i][0]: 若第i-1天已持有股票则dp[i][0]dp[i-1][0]; 若第i-1天未持有股票则dp[i][0]dp[i-1][1]-prices[i];综上,dp[i][0]fmax(dp[i-1][0],dp[i-1][1]-prices[i]);(II与I的唯一区别就在于: 只允许一次购买时,在持有股票之前所获得利润必为0,而允许多次购买则不然)对于dp[i][1]: 若第i-1天未持有股票则dp[i][1]dp[i-1][1]; 若第i-1天已持有股票则dp[i][1]dp[i-1][0]prices[i];综上:dp[i][1]fmax(dp[i-1][1],dp[i-1][0]prices[i]);3.初始化:dp[0][0]-prices[0];算法实现int maxProfitII(int *prices,int pricesSize){//设置两种状态:0表示已持有股票1表示未持有股票//1.dp[i][0]表示第i天已持有股票时获得的最大利润//dp[i][1]表示第i天未持有股票时获得的最大利润//2.递推式://对于dp[i][0]:// 若第i-1天已持有股票则dp[i][0]dp[i-1][0];// 若第i-1天未持有股票则dp[i][0]dp[i-1][1]-prices[i];//综上,dp[i][0]fmax(dp[i-1][0],dp[i-1][1]-prices[i]);//(II与I的唯一区别就在于:// 只允许一次购买时,在持有股票之前所获得利润必为0,而允许多次购买则不然)//对于dp[i][1]:// 若第i-1天未持有股票则dp[i][1]dp[i-1][1];// 若第i-1天已持有股票则dp[i][1]dp[i-1][0]prices[i];//综上:dp[i][1]fmax(dp[i-1][1],dp[i-1][0]prices[i]);//3.初始化://dp[0][0]-prices[0];int dp[pricesSize][2];memset(dp,0,sizeof(dp));dp[0][0]-prices[0];for(int i1;ipricesSize;i){dp[i][0]fmax(dp[i-1][0],dp[i-1][1]-prices[i]);dp[i][1]fmax(dp[i-1][1],dp[i-1][0]prices[i]);}return dp[pricesSize-1][1]; }三、最多买卖两次题目链接123. 买卖股票的最佳时机 III - 力扣LeetCode算法思想设置四种状态: 0表示第一次已持有股票 1表示第一次未持有股票 2表示第二次已持有股票 3表示第二次未持有股票1.dp[i][0]表示第i天第一次已持有股票时获得的最大利润dp[i][1]表示第i天第一次未持有股票时获得的最大利润dp[i][2]表示第i天第二次已持有股票时获得的最大利润dp[i][3]表示第i天第二次未持有股票时获得的最大利润2.递推式:对于dp[i][0]: 若第i-1天第一次已持有股票则dp[i][0]dp[i-1][0]; 若第i-1天第一次未持有股票则dp[i][0]0-prices[i];综上,dp[i][0]fmax(dp[i-1][0],-prices[i]);对于dp[i][1]: 若第i-1天第一次未持有股票则dp[i][1]dp[i-1][1]; 若第i-1天第一次已持有股票则dp[i][1]dp[i-1][0]prices[i];综上,dp[i][1]fmax(dp[i-1][1],dp[i-1][0]prices[i]);对于dp[i][2]: 若第i-1天第一次已持有股票则dp[i][2]dp[i-1][2]; 若第i-1天第一次未持有股票则dp[i][2]dp[i-1][1]-prices[i];综上,dp[i][2]fmax(dp[i-1][2],dp[i-1][1]-prices[i]);对于dp[i][3]: 若第i-1天第一次未持有股票则dp[i][3]dp[i-1][3]; 若第i-1天第一次已持有股票则dp[i][3]dp[i-1][2]prices[i];综上:dp[i][3]fmax(dp[i-1][3],dp[i-1][2]prices[i]);3.初始化:dp[0][0]dp[0][2]-prices[0];算法实现int maxProfitIII(int *prices,int pricesSize){//设置四种状态:// 0表示第一次已持有股票// 1表示第一次未持有股票// 2表示第二次已持有股票// 3表示第二次未持有股票//1.dp[i][0]表示第i天第一次已持有股票时获得的最大利润//dp[i][1]表示第i天第一次未持有股票时获得的最大利润//dp[i][2]表示第i天第二次已持有股票时获得的最大利润//dp[i][3]表示第i天第二次未持有股票时获得的最大利润//2.递推式://对于dp[i][0]:// 若第i-1天第一次已持有股票则dp[i][0]dp[i-1][0];// 若第i-1天第一次未持有股票则dp[i][0]0-prices[i];//综上,dp[i][0]fmax(dp[i-1][0],-prices[i]);//对于dp[i][1]:// 若第i-1天第一次未持有股票则dp[i][1]dp[i-1][1];// 若第i-1天第一次已持有股票则dp[i][1]dp[i-1][0]prices[i];//综上,dp[i][1]fmax(dp[i-1][1],dp[i-1][0]prices[i]);//对于dp[i][2]:// 若第i-1天第一次已持有股票则dp[i][2]dp[i-1][2];// 若第i-1天第一次未持有股票则dp[i][2]dp[i-1][1]-prices[i];//综上,dp[i][2]fmax(dp[i-1][2],dp[i-1][1]-prices[i]);//对于dp[i][3]:// 若第i-1天第一次未持有股票则dp[i][3]dp[i-1][3];// 若第i-1天第一次已持有股票则dp[i][3]dp[i-1][2]prices[i];//综上:dp[i][3]fmax(dp[i-1][3],dp[i-1][2]prices[i]);//3.初始化://dp[0][0]dp[0][2]-prices[0];int dp[pricesSize][4];memset(dp,0,sizeof(dp));dp[0][0]dp[0][2]-prices[0];for(int i1;ipricesSize;i){dp[i][0]fmax(dp[i-1][0],-prices[i]);dp[i][1]fmax(dp[i-1][1],dp[i-1][0]prices[i]);dp[i][2]fmax(dp[i-1][2],dp[i-1][1]-prices[i]);dp[i][3]fmax(dp[i-1][3],dp[i-1][2]prices[i]);}return dp[pricesSize-1][3]; }四、最多买卖k次题目链接188. 买卖股票的最佳时机 IV - 力扣LeetCode算法思想设置2*k种状态: for j1 to k 2*j-1表示第j次已持有股票 2*j1表示第j次未持有股票1.dp[i][2*j-1]表示第i天第j次已持有股票时获得的最大利润dp[i][2*j]表示第i天第j次未持有股票时获得的最大利润2.递推式:对于dp[i][2*j-1]: 若第i-1天第j次已持有股票则dp[i][2*j-1]dp[i-1][2*j-1]; 若第i-1天第j次未持有股票则dp[i][2*j-1]dp[i-1][2*j-2]-prices[i];综上,dp[i][2*j-1]fmax(dp[i-1][2*j-1],dp[i-1][2*j-2]-prices[i]);对于dp[i][2*j]: 若第i-1天第j次未持有股票则dp[i][2*j]dp[i-1][2*j]; 若第i-1天第j次已持有股票则dp[i][2*j]dp[i-1][2*j-1]prices[i];综上,dp[i][2*j]fmax(dp[i-1][2*j],dp[i-1][2*j-1]prices[i]);3.初始化:for(int i1;i2*k;i2) dp[0][i]-prices[0];算法实现实际上就是在三的基础上从2次买卖延伸到了k次买卖用for循环即可int maxProfitIV(int k,int *prices,int pricesSize){//设置2*k种状态:// for j1 to k// 2*j-1表示第j次已持有股票// 2*j1表示第j次未持有股票//1.dp[i][2*j-1]表示第i天第j次已持有股票时获得的最大利润//dp[i][2*j]表示第i天第j次未持有股票时获得的最大利润//2.递推式://对于dp[i][2*j-1]:// 若第i-1天第j次已持有股票则dp[i][2*j-1]dp[i-1][2*j-1];// 若第i-1天第j次未持有股票则dp[i][2*j-1]dp[i-1][2*j-2]-prices[i];//综上,dp[i][2*j-1]fmax(dp[i-1][2*j-1],dp[i-1][2*j-2]-prices[i]);//对于dp[i][2*j]:// 若第i-1天第j次未持有股票则dp[i][2*j]dp[i-1][2*j];// 若第i-1天第j次已持有股票则dp[i][2*j]dp[i-1][2*j-1]prices[i];//综上,dp[i][2*j]fmax(dp[i-1][2*j],dp[i-1][2*j-1]prices[i]);//3.初始化://for(int i1;i2*k;i2) dp[0][i]-prices[0];int dp[pricesSize][2*k1];memset(dp,0,sizeof(dp));for(int i1;i2*k;i2)dp[0][i]-prices[0];for(int i1;ipricesSize;i){for(int j1;jk;j){dp[i][2*j-1]fmax(dp[i-1][2*j-1],dp[i-1][2*j-2]-prices[i]);dp[i][2*j]fmax(dp[i-1][2*j],dp[i-1][2*j-1]prices[i]);}}return dp[pricesSize-1][2*k]; }五、买卖多次卖出有一天冷冻期题目链接309. 最佳买卖股票时机含冷冻期 - 力扣LeetCode算法思想设置三种状态: 0表示已持有股票 1表示未持有股票且处于非冷冻状态 2表示未持有股票且处于冷冻状态1.dp[i][0]表示第i天已持有股票时获得的最大利润dp[i][1]表示第i天未持有股票且处于非冷冻状态时获得的最大利润dp[i][2]表示第i天未持有股票且处于冷冻状态时获得的最大利润2.递推式:对于dp[i][0]: 若第i-1天已持有股票则dp[i][0]dp[i-1][0]; 若第i-1天未持有股票必为非冷冻状态则dp[i][0]dp[i-1][1]-prices[i];综上,dp[i][0]fmax(dp[i-1][0],dp[i-1][1]-prices[i]);对于dp[i][1]: 第i-1天必未持有股票 若第i-1天未持有股票且处于非冷冻状态则dp[i][1]dp[i-1][1]; 若第i-1天未持有股票且处于冷冻状态则dp[i][1]dp[i-1][2];综上:dp[i][1]fmax(dp[i-1][1],dp[i-1][2]);对于dp[i][2]: 第i-1天必已持有股票则dp[i][2]dp[i-1][0]prices[i];3.初始化:dp[0][0]-prices[0];算法实现int maxProfitV(int *prices,int pricesSize){//设置三种状态:// 0表示已持有股票// 1表示未持有股票且处于非冷冻状态// 2表示未持有股票且处于冷冻状态//1.dp[i][0]表示第i天已持有股票时获得的最大利润//dp[i][1]表示第i天未持有股票且处于非冷冻状态时获得的最大利润//dp[i][2]表示第i天未持有股票且处于冷冻状态时获得的最大利润//2.递推式://对于dp[i][0]:// 若第i-1天已持有股票则dp[i][0]dp[i-1][0];// 若第i-1天未持有股票必为非冷冻状态则dp[i][0]dp[i-1][1]-prices[i];//综上,dp[i][0]fmax(dp[i-1][0],dp[i-1][1]-prices[i]);//对于dp[i][1]:// 第i-1天必未持有股票// 若第i-1天未持有股票且处于非冷冻状态则dp[i][1]dp[i-1][1];// 若第i-1天未持有股票且处于冷冻状态则dp[i][1]dp[i-1][2];//综上:dp[i][1]fmax(dp[i-1][1],dp[i-1][2]);//对于dp[i][2]:// 第i-1天必已持有股票则dp[i][2]dp[i-1][0]prices[i];//3.初始化://dp[0][0]-prices[0];int dp[pricesSize][3];memset(dp,0,sizeof(dp));dp[0][0]-prices[0];for(int i1;ipricesSize;i){dp[i][0]fmax(dp[i-1][0],dp[i-1][1]-prices[i]);dp[i][1]fmax(dp[i-1][1],dp[i-1][2]);dp[i][2]dp[i-1][0]prices[i];}return fmax(dp[pricesSize-1][1],dp[pricesSize-1][2]); }六、买卖多次卖出有手续费题目链接714. 买卖股票的最佳时机含手续费 - 力扣LeetCode算法思想同二算法实现如果掌握了二那么这题就不用看int maxProfitVI(int *prices,int pricesSize,int fee){//设置两种状态:0表示已持有股票1表示未持有股票//1.dp[i][0]表示第i天已持有股票时获得的最大利润//dp[i][1]表示第i天未持有股票时获得的最大利润//2.递推式://对于dp[i][0]:// 若第i-1天已持有股票则dp[i][0]dp[i-1][0];// 若第i-1天未持有股票则dp[i][0]dp[i-1][1]-prices[i];//综上,dp[i][0]fmax(dp[i-1][0],dp[i-1][1]-prices[i]);//对于dp[i][1]:// 若第i-1天未持有股票则dp[i][1]dp[i-1][1];// 若第i-1天已持有股票则dp[i][1]dp[i-1][0]prices[i]-fee;//综上:dp[i][1]fmax(dp[i-1][1],dp[i-1][0]prices[i]-fee);//3.初始化://dp[0][0]-prices[0];int dp[pricesSize][2];memset(dp,0,sizeof(dp));dp[0][0]-prices[0];for(int i1;ipricesSize;i){dp[i][0]fmax(dp[i-1][0],dp[i-1][1]-prices[i]);dp[i][1]fmax(dp[i-1][1],dp[i-1][0]prices[i]-fee);}return dp[pricesSize-1][1]; }