1 买卖股票的最佳时机

LeetCode:买卖股票的最佳时机
本题之前已经使用过贪心处理过了，这里使用动态规划思维解决。
本题可以将每天的状态分为持有股票和不持有股票，不同状态下每天所剩余的最大现金分别使用dp[i][0]与dp[i][1]表示。

• 那么针对不持有，分为第i-1天不持有且第i天不操作和第i-1天持有且第i天抛出两种情况，那么递推公式为dp[i][0] = max( dp[i-1][0], dp[i-1][1] + prices[i] )。
• 而针对持有，分为第i-1天持有且第i天不操作和前i-1天均持有且第i天买入两种情况，dp[i][1] = max( dp[i-1][1], -prices[i] )

值得注意的是，本题只能买入一次股票，因此买入时的现金必然为-prices[i]。

class Solution {
public:int maxProfit(vector& prices) {//dp[i][0]代表第i天持有股票时，所剩余的现金//dp[i][0]意味着【昨天不持有+今天买入】或【昨天持有】//因为只能买入一次，所以【昨天不持有+今天买入】= 0 - prices[i]//故dp[i][0]=max( dp[i-1][0] , dp[i-1][1] - prices[i] )//dp[i][1]代表第i天不持有股票时，所剩余的现金//dp[i][1]意味着【昨天持有+今天卖出】或【昨天不持有+今天不买入】//故dp[i][1] = max( dp[i-1][0] + prices[i] , dp[i-1][1])//因为只用到了dp[i-1]，所以可以节省空间//初始化vector dp(2,0);dp[0]=-prices[0];dp[1]=0;for(int i=1;idp[1] = max(dp[1],dp[0]+prices[i]);dp[0] = max(dp[0] ,0 -prices[i]);}return dp[1];}
};

2 买卖股票的最佳时机II

LeetCode:买卖股票的最佳时机II
与上一题的区别在于可以买入多次，因此买入时的现金为dp[i-1][0]-prices[i]。

class Solution {
public:int maxProfit(vector& prices) {//使用动态规划//dp[i][0]为【第i天持有时现金】，dp[i][1]为【第i天不持有时现金】//dp[i][0] = max( dp[i-1][0] , dp[i-1][1]-prices[i] )//dp[i][1] = max( dp[i-1][1] , dp[i-1][0]+prices[i] )vector dp(2,0);dp[0]=-prices[0];dp[1]=0;for(int i=0;iint tmp=dp[0];dp[0] = max(dp[0],dp[1]-prices[i]);dp[1] = max(dp[1],tmp+prices[i]);}return dp[1];}
};

3 买卖股票的最佳时机III

LeetCode:买卖股票的最佳时机III
限定次数的情况，在持有与不持有两种状态的基础上，进一步考虑第一次交易和第二次交易，因此共4种状态。
代码中有详细注释

class Solution {
public:int maxProfit(vector& prices) {//dp[i][0]代表第i天第一次持有时最大现金，dp[i][1]代表第二次持有时最大现金//dp[i][2]代表第一次抛出后第i天不持有时最大现金，dp[i][3]代表第二次抛出后第i天不持有时最大现金//dp[i][0] = max(dp[i-1][0] , 0 - princes[i])//dp[i][1] = max(dp[i-1][1] , dp[i-1][2] - princes[i])//dp[i][2] = max(dp[i-1][2] , dp[i-1][0] + princes[i])//dp[i][3] = max(dp[i-1][3] , dp[i-1][1] + princes[i])//综上,改变顺序应改为dp[3]->dp[1]->dp[2]->dp[0]vector dp(4,0);dp[0] = -prices[0];dp[1] = -prices[0];dp[2] = 0;dp[3] = 0;for(int i = 1 ; idp[3] = max(dp[3],dp[1]+prices[i]);dp[1] = max(dp[1],dp[2]-prices[i]);dp[2] = max(dp[2],dp[0]+prices[i]);dp[0] = max(dp[0],-prices[i]);}return max(dp[2],dp[3]);}
};

4 买卖股票的最佳时机IV

LeetCode:买卖股票的最佳时机IV
和上一题没有区别，值得注意的是规范状态的排列顺序，方便递推公式的写法。
另外，因为考虑到第一天进行了若干次的收益为0的模拟买入卖出，所以最后一次（第k次）卖出一定可以得到最多的价值。

class Solution {
public:int maxProfit(int k, vector& prices) {//特殊情况排除if(k==0 || prices.size()<=1)return 0;//dp[i][2*k]代表第i天第k+1次交易时持有，dp[i][2*k+1]代表第i天第k+1次抛出后不持有//dp[i][2*k] = max(dp[i-1][2*k] , dp[i-1][2*k-1] - princes[i])//dp[i][2*k+1] = max(dp[i-1][2*k+1] , dp[i-1][2*k] + princes[i])vector dp(2*k,0);//初始化，持有均为-prices[0]for(int i=0;idp[2*i] = -prices[0];}for(int i=1;ifor(int j=2*k-1;j>=1;j=j-2){dp[j] = max(dp[j] , dp[j-1] + prices[i]);if(j!=1)dp[j-1] = max(dp[j-1] , dp[j-2]-prices[i]);elsedp[j-1] = max(dp[j-1] , -prices[i]);}}return dp[2*k-1];}
};

5 最佳买卖股票时机含冷冻期

LeetCode:最佳买卖股票时机含冷冻期
考虑冷冻期，因此考虑三种状态：

• dp[i][0]为第i天持有状态下的最大现金。
• dp[i][1]为第i天卖出状态下的最大现金（卖出状态也是未持有状态中的一种）。
• dp[i][2]为第i天不卖出+不持有状态下的最大现金（即明天第i+1天不是冷冻期）
• 递推公式为：
  • dp[i][0] = max( dp[i-1][0] , dp[i-1][2] - prices[i] )
  • dp[i][1] = dp[i-1][0] + prices[i]
  • dp[i][2] = max( dp[i-1][2] , dp[i-1][1] )

class Solution {
public:int maxProfit(vector& prices) {//dp[i][0]代表第i天持有时的最大现金//dp[i][1]代表第i天【卖出】导致不持有时的最大现金//dp[i][2]代表第i天【不操作】且【不持有】时的最大现金(即第i+1天不是冷冻期的不持有)//dp[i][0] = max( dp[i-1][0] , dp[i-1][2] - prices[i])//dp[i][1] = dp[i-1][0] + prices[i]//dp[i][2] = max( dp[i-1][2] , dp[i-1][1])vector dp(3,0);dp[0]=-prices[0];dp[1]=0;dp[2]=0;for(int i=1;iint tmp=dp[0];dp[0] = max(dp[0],dp[2]-prices[i]);dp[2] = max(dp[2],dp[1]);dp[1] = tmp + prices[i];}return max(dp[1],dp[2]);}
};

6 买卖股票的最佳时机含手续费

LeetCode:买卖股票的最佳时机含手续费
将手续费融入买入价或者卖出价中，就与问题买卖股票的最佳时机II没有任何区别了。

class Solution {
public:int maxProfit(vector& prices, int fee) {//手续费fee，在每次买入的时候就扣除//dp[0]代表持有，dp[i][0]=max(dp[i-1][0],dp[i-1][1]-princes[i]-fee)//dp[1]代表不持有，dp[i][1] = max(dp[i-1][1] , dp[i-1][0] + princes[i])vector dp(2,0);dp[0]=-prices[0]-fee;dp[1]=0;for(int i = 1 ; iint tmp=dp[0];dp[0] = max( tmp , dp[1] - prices[i] - fee);dp[1] = max( dp[1], tmp+prices[i]);}return dp[1];}
};

7 总结

股票问题就这样了，找好每一天的状态分类与递推公式即可。
今天去游泳馆体验了一下，感觉出来后感觉耳朵怪怪的。
——2023.3.5