188. 买卖股票的最佳时机 IV

 

解释见代码：

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if(prices.size()==0||k==0)
            return 0;
        if(k>=prices.size()/2)
        {
            int dp[prices.size()+10][3];
            dp[0][0]=0;
            dp[0][1]=-prices[0];
            for(int i=1;i<prices.size();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]);
            }
            return dp[prices.size()-1][0];
        }//无限次交易 
        int dp[prices.size()+10][2][k+10];//i天  手上是否有票  当前是第几次交易
        for(int i=0;i<=k;i++)//初始化
        {
            dp[0][0][i]=0;//第一天手上没票的利润为0 不管交易多少次
            dp[0][1][i]=-prices[0];//第一天手上有票利润为负的成本 不管交易多少次
        }
        for(int i=1;i<prices.size();i++)
        {
            for(int j=0;j<=k;j++)//k次交易
            {
                if(j==0)
                    dp[i][0][j]=dp[i-1][0][j];//第0次交易手上没票的话 状态为上一次的状态
                else
                    dp[i][0][j]=max(dp[i-1][0][j],dp[i-1][1][j-1]+prices[i]);//第j次交易手上没票:1.前一天也没票交易今天也没票，因此还是j次交易 2.前一天手上有票，今天卖掉，前一天的交易次数是j-1，加上今天之后的是j次  
                dp[i][1][j]=max(dp[i-1][1][j],dp[i-1][0][j]-prices[i]);//第j次交易手上有票：1.前一天也有票，今天也有票，没卖掉，那么还是j次交易 2.前一天手上没票，今天买入，买入不算一次交易还是j次交易
            }
        }
        int maxx=0;
        for(int i=0;i<=k;i++)
        {
            maxx=max(maxx,dp[prices.size()-1][0][i]);//取每次交易的最大值
        }
        return maxx;
    }
};