酒店和网站对接如何做,APP网站怎么做,网站设计公司 南京,wordpress 好用插件推荐题目1#xff1a;123 买卖股票的最佳时机Ⅲ
题目链接#xff1a;买卖股票的最佳时机Ⅲ
对题目的理解
prices[i]表示股票在第i天的价格#xff0c;最多可以完成两笔交易#xff0c;不能同时进行多笔交易
可以买卖一次#xff0c;两次#xff0c;也可以不买卖
动态规划…题目1123 买卖股票的最佳时机Ⅲ
题目链接买卖股票的最佳时机Ⅲ
对题目的理解
prices[i]表示股票在第i天的价格最多可以完成两笔交易不能同时进行多笔交易
可以买卖一次两次也可以不买卖
动态规划
动规五部曲
1dp数组及下标i的含义
dp[i][0] 不操作(可有可无)股票的最大现金
dp[i][1] 第一次持有股票的最大现金
dp[i][2] 第一次不持有股票的最大现金
dp[i][3] 第二次持有股票的最大现金
dp[i][4] 第二次不持有股票的最大现金
不持有股票现金的状态一定比持有股票的现金多第二次不持有一定包含第一次不持有的钱
最终求解 dp[prices.size()-1][4]
2递推公式
dp[i][0] dp[i-1][0]
dp[i][1] dp[i-1][1] 前一天已经持有
dp[i][1] dp[i-1][0]-prices[i] 第i天买入,前一天不操作
dp[i][1] max(dp[i-1][1]dp[i-1][0]-prices[i])
dp[i][2] dp[i-1][2] 前一天不持有
dp[i][2] dp[i-1][1]prices[i] 第i天卖出 前一天持有
dp[i][2] max(dp[i-1][2]dp[i-1][1]prices[i])
dp[i][3] dp[i-1][3] 前一天已经持有
dp[i][3] dp[i-1][2] -prices[i] 第i天买入但是因为是第二次买入所以应该是在第一次卖出的基础上减去第i天的股票价格
dp[i][3] max(dp[i-1][3]dp[i-1][2]-prices[i])
dp[i][4] dp[i-1][4] 前一天不持有
dp[i][4] dp[i-1][3] prices[i] 第i天卖出但是因为是第二次卖出所以应该在第二次买入的基础上加上第i天的股票价格
dp[i][4] max(dp[i-1][4]dp[i-1][3]prices[i])
3dp数组初始化
从递推公式可以看出i的状态由i-1的状态决定所以初始化dp[0]
dp[0][0]0
dp[0][1]-prices[0]
dp[0][2]0(同一天买卖)
dp[0][3]-prices[0](第二次又买入了)
dp[0][4]0第二次又卖出了
4遍历顺序
从递推公式可以看出i的状态由i-1的状态决定所以从小到大遍历
for(i1;iprices.size();i) 注意从1开始
5打印dp数组
代码
class Solution {
public:int maxProfit(vectorint prices) {//定义dp数组vectorvectorint dp(prices.size(),vectorint(5));//初始化dp数组dp[0][0] 0;//不操作dp[0][1] -prices[0];//第一次持有股票dp[0][2] 0;//第一次不持有股票dp[0][3] -prices[0];//第二次持有股票dp[0][4] 0;//第二次不持有股票for(int i1;iprices.size();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[prices.size()-1][4];}
};
时间复杂度O(n)空间复杂度O(n × 5)
不使用dp[i][0]这个数组直接将dp[i][0]相关的部分注释掉即可
代码
class Solution {
public:int maxProfit(vectorint prices) {//定义dp数组vectorvectorint dp(prices.size(),vectorint(5));//初始化dp数组// dp[0][0] 0;//不操作dp[0][1] -prices[0];//第一次持有股票dp[0][2] 0;//第一次不持有股票dp[0][3] -prices[0];//第二次持有股票dp[0][4] 0;//第二次不持有股票for(int i1;iprices.size();i){// dp[i][0] dp[i-1][0];dp[i][1] max(dp[i-1][1],-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[prices.size()-1][4];}
};
题目2买卖股票的最佳时机Ⅳ
题目链接买卖股票的最佳时机Ⅳ
对题目的理解
prices[i]是某支股票在第i天的价格最多可以完成k笔交易不能同时参与多笔交易
动规五部曲
1dp数组及下标i的含义
dp[i][j]:第i天的状态为j持有股票奇数不持有股票偶数所拥有的最大现金j大于等于0小于等于2k
最终求解dp[prices.size()-1][2k]
2递推公式
for(j0;j2k-1;j2) //j控制第几次买卖
第j次持有 dp[i][j1] max(dp[i-1][j1],dp[i][j]-prices[i]);
第j次不持有 dp[i][j2] max(dp[i-1][j2],dp[i][j1]prices[i]);
3dp数组初始化
根据递推公式j为奇数表示持有for(int j1;j2k;j2) dp[0][j]-prices[0]
4遍历顺序
根据递推公式从小到大遍历
5打印dp数组
代码
class Solution {
public:int maxProfit(int k, vectorint prices) {//定义dp数组vectorvectorint dp(prices.size(),vectorint(2*k1));//初始化dp数组for(int j1;j2*k;j2){//j为奇数下标时全为-prices[0],j是下标应不超过2k1dp[0][j]-prices[0];} //递推for(int i1;iprices.size();i){for(int j0;j2*k-1;j2){//将j代入j2,2k-222k//持有dp[i][j1]max(dp[i-1][j1],dp[i-1][j]-prices[i]);//不持有dp[i][j2]max(dp[i-1][j2],dp[i-1][j1]prices[i]);}}return dp[prices.size()-1][2*k];}
};
时间复杂度: O(n * k)其中 n 为 prices 的长度空间复杂度: O(n * k)
