买卖股票的最佳时机四

之前是最多只能完成两笔交易，现在是至多可以买卖k次，那么状态数需要定为2*k+1种，此时，就要分析多种情况的递推式
找到奇偶数交替的规则即可

class Solution {
public:int maxProfit(int k, vector<int>& prices) {if(prices.size()==0) return 0;vector<vector<int>> dp(prices.size(),vector<int>(2*k+1,0));for(int j=1;j<2*k;j+=2){dp[0][j]=-prices[0];}for(int i=1;i<prices.size();++i){for(int j=0;j<2*k-1;j+=2){dp[i][j+1]=max(dp[i-1][j+1],dp[i-1][j]-prices[i]);dp[i][j+2]=max(dp[i-1][j+2],dp[i-1][j+1]+prices[i]);}}return dp[prices.size()-1][2*k];}
};

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

如何去分离状态使得包含所有情况，又能更简单的得到递推式

class Solution {
public:int maxProfit(int k, vector<int>& prices) {if(prices.size()==0) return 0;vector<vector<int>> dp(prices.size(),vector<int>(2*k+1,0));for(int j=1;j<2*k;j+=2){dp[0][j]=-prices[0];}for(int i=1;i<prices.size();++i){for(int j=0;j<2*k-1;j+=2){dp[i][j+1]=max(dp[i-1][j+1],dp[i-1][j]-prices[i]);dp[i][j+2]=max(dp[i-1][j+2],dp[i-1][j+1]+prices[i]);}}return dp[prices.size()-1][2*k];}
};

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

动态规划理解起来比贪心简单很多
只需加一个扣手续费即可

class Solution {
public:int maxProfit(vector<int>& prices, int fee) {int n=prices.size();vector<vector<int>> dp(n,vector<int>(2,0));dp[0][0]=-prices[0];for(int i=1;i<n;++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]-fee);}return max(dp[n-1][0],dp[n-1][1]);}
};