力扣（123.188）补8.4

123.买卖股票的最佳时机Ⅲ

这题我感觉一知半解吧。毕竟也是困难题。好像是默认每天顶多只有一次买或卖，要不然没有意义。

因为我一开始想在一天内又买又卖，不就不符合答案的dp迭代式了嘛。。。

class Solution {

public:

    int maxProfit(vector& prices) {

        int n=prices.size();

        vector>>dp(n,vector>(2,vector(3,0)));

        dp[0][0][0]=0;

        dp[0][0][1]=INT_MIN+100000;

        dp[0][0][2]=INT_MIN;

        dp[0][1][0]=-prices[0];

        dp[0][1][1]=INT_MIN;

        dp[0][1][2]=INT_MIN;

        for(int i=1;i

            dp[i][0][0]=0;

            dp[i][0][1]=max(dp[i-1][1][0]+prices[i],dp[i-1][0][1]);

            dp[i][0][2]=max(dp[i-1][1][1]+prices[i],dp[i-1][0][2]);

            dp[i][1][0]=max(dp[i-1][0][0]-prices[i],dp[i-1][1][0]);

            dp[i][1][1]=max(dp[i-1][0][1]-prices[i],dp[i-1][1][1]);

            dp[i][1][2]=INT_MIN;

        }

        return max(max(dp[n-1][0][1],dp[n-1][0][2]),0);

这里还要和0比较，容易忘。

    }

};

 

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

我解释一下dp（i）（j），就是第i天结束的状态j，但状态j可能是当天达到的，也有可能是之前达到的。

这里好像是默认每天顶多只会进行一次买入或卖出，要不然应该没有意义。

 

class Solution {

public:

    int maxProfit(int k, vector& prices) {

        int n=prices.size();

        vector>dp(n,vector(2*k+1,0));

        if(n==0)

        return 0；

这里容易忘。

        for(int i=1;i<2*k;i+=2)

        dp[0][i]=-prices[0];

        for(int i=1;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[n-1][2*k];

交易最大次数后的一定是最优解。因为每次交易都是当前最优解。

    }

};