深圳网站建设怎样容易,wordpress不使用缩略图,装修类网站模板下载,青岛优化网站关键词123.买卖股票的最佳时机|||
分析#xff1a;只能买卖两次#xff0c;就是说有五个状态#xff1a;
没有买过第一次买入第一次卖出第二次买入第二次卖出
思路#xff1a;二维数组#xff0c;记录五个状态
1.dp存储#xff1a;dp[i][1] 第一次买入 dp[i][2] 第一次卖…123.买卖股票的最佳时机|||
分析只能买卖两次就是说有五个状态
没有买过第一次买入第一次卖出第二次买入第二次卖出
思路二维数组记录五个状态
1.dp存储dp[i][1] 第一次买入 dp[i][2] 第一次卖出 dp[i][3] 第二次买入 dp[i][4] 第二次卖出2.dp[i][1]max(dp[i-1][1],dp[i-1][0]-prices[i]) dp[i][2]max(dp[i-1][2],dp[i-1][1]prices[i])dp[i][3]max(dp[i-1][3],dp[i-1][2]-prices[i])dp[i][4]max(dp[i-1][4],dp[i-1][3]prices[i])3.初始化dp[0][1]-prices[0] dp[0][3]-prices[0]4.遍历顺序1~n
class Solution {
public:int maxProfit(vectorint prices) {int nprices.size();vectorvectorint dp(n,vectorint(5,0));dp[0][1]-prices[0];dp[0][3]-prices[0];for(int i1;in;i){dp[i][0]dp[i-1][0];//第一天不持有dp[i][1]max(dp[i-1][1],dp[i-1][0]-prices[i]);dp[i][2]max(dp[i-1][2],dp[i-1][1]prices[i]);dp[i][3]max(dp[i-1][3],dp[i-1][2]-prices[i]);dp[i][4]max(dp[i-1][4],dp[i-1][3]prices[i]);}return dp[n-1][4];}
}; 188.买卖股票的最佳时机IV
分析买卖几次成了变量
思路
1.dp存储2k1个状态的买卖金额2.动态转移方程递推式 j奇数dp[i][j]max(dp[i-1][j],dp[i-1][j-1]-prices[i]) j偶数dp[i][j]max(dp[i-1][j],dp[i-1][j-1]prices[i])3.初始化j奇数dp[i][j]-prices[0]4.遍历顺序1-n
class Solution {
public:int maxProfit(int k, vectorint prices) {int nprices.size();int mk*2;vectorvectorintdp(n,vectorint(m1,0));for(int i1;im;i2) dp[0][i]-prices[0]; //初始化for(int i1;in;i){dp[i][0]dp[i-1][0];//第一天不持有for(int j1;jm1;j){if(j%2!0) dp[i][j]max(dp[i-1][j],dp[i-1][j-1]-prices[i]);//第j天持有else dp[i][j]max(dp[i-1][j],dp[i-1][j-1]prices[i]);//第j天卖出}}return dp[n-1][m];}
}; 309.买卖股票的最佳时机含冷冻期
分析现在有四种状态买入股票 冷冻期后没买入 卖出股票 冷冻期
思路dp存储四种状态
1.dp存储四种状态2.动态转移方程递推式: dp[i][0]max(dp[i-1][0],max(dp[i-1][1]-prices[i],dp[i-1][3]-prices[i]))dp[i][1]max(dp[i-1][1],dp[i-1][3])dp[i][2]dp[i-1][0]prices[i]dp[i][3]dp[i-1][2]3.初始化dp[0][0]-prices[0]4.遍历顺序1~n
class Solution {
public:int maxProfit(vectorint prices) {int nprices.size();vectorvectorintdp(n,vectorint(4,0));dp[0][0]-prices[0];for(int i1;in;i){dp[i][0]max(dp[i-1][0],max(dp[i-1][1]-prices[i],dp[i-1][3]-prices[i]));//持有dp[i][1]max(dp[i-1][1],dp[i-1][3]);//冷冻期后面不持有dp[i][2]dp[i-1][0]prices[i];//卖出dp[i][3]dp[i-1][2];//冷冻期}return max(dp[n-1][3],max(dp[n-1][1],dp[n-1][2]));//最大值一定不持有}
};
