什么叫手撕代码?就是做不出来很烦躁🤬就想把这题给撕了炖了🍲 炖了炖了🍲🍲🍲🍲🍲🍲🍲
    188. 买卖股票的最佳时机 IV - 图1
    分享一下解法,有用三维数组的,也有用二维数组的,还有用一维数组的

    emmm,先抛出一个问题,不知道你们有没有理解题目到底怎么定义的交易?
    若:
    买+卖 = 一次交易
    那么:
    一次买 = 几次交易?🌝0.5?
    一次卖 = 几次交易?🌝0.5?

    若:
    一次买 = 一次交易
    一次卖 = 一次交易
    那么:
    买 + 卖 = 几次交易?🌝

    先啃个水果压压惊🥑🥑🥑,哼,这个地方就是个坑,我在这个坑里面蹲了好久才爬出来
    这里是需要我们自己去完善这个定义从而建立我们的dp数组的

    三维数组的解法:
    如果我们把买+卖算一次交易
    那么这道题的限制是交易数,天数,手上有没有股票(有股票就不能买,没有股票就不能卖)
    建立三维的数组:dp[k][i][2]
    其中k表示的是交易次数,i表示的是第几天,2表示的是有两种状态:手上没有股票/手上有股票
    dp[k][i][0] 数组中的数字表示的是到了第i天,交易了k次,手上没有股票获得的最大利益
    dp[k][i][1] 数组中的数字表示的是到了第i天,交易了k次,手上持有股票获得的最大利益
    在我们写转移方程之前我们还要先考虑之前提出来的问题—交易数怎么算,买+卖是一次交易,我的t表示的是交易次数,那我到底是买入的时候t要加一了,还是卖出的时候t才加一?

    答:都可以,不同的定义就会有不同的实现

    来看一下两者有什么不同
    1>买入就算一次交易:
    i天t次交易现在手上不持有 = max(i-1天t次交易手上不持有,i-1天t次交易手上持有 + i天卖出价格prices)
    dp[t][i][0] = max(dp[t][i - 1][0], dp[t][i - 1] + prices[i]);

    i天t次交易现在手上持有 = max(i-1天t次交易手上持有,i-1天t-1次交易手上不持有 - i天买入价格)
    dp[t][i][1] = max(dp[t][i - 1][1], dp[t - 1][i - 1][0] - prices[i])

    2>买入后卖出才算一次交易
    i天t次交易现在手上不持有 = max(i天t次交易手上不持有,i - 1天t - 1次交易 + i天卖出)
    dp[t][i][0] = max(dp[t][i][0], dp[t - 1][i - 1][1] + prices[i])

    i天t次交易现在手上持有 = max(i天t次交易现在手上持有,i - 1天t次交易 + i天买入)
    dp[t][i][1] = max(dp[t][i][1], dp[t][i - 1][0] - prices[i])

    除了转移方程不一样以外,还有初始状态不一样
    1>买入就算一次交易:
    dp[t][0][0] 0天t次交易,手上不持有:可能的 0
    dp[t][0][1] 0天t次交易,手上持有:不可能(0天没有股票,所以无法买入持有;持有说明至少进行了一次买入,买入就交易,因此这里不可能【不可能意思就是不能从这里转移】
    dp[0][i][0] i天0次交易,手上不持有:0
    dp[0][i][1] i天0次交易,手上持有:不可能(不交易手上不可能持有)

    1. class Solution {
    2. public:
    3. int maxProfit(int k, vector<int>& prices) {
    4. if(!prices.size()) return 0;
    5. if(k >= prices.size()/2)
    6. {
    7. int sum = 0;
    8. for(int i = 1; i < prices.size(); i++)
    9. {
    10. int val = prices[i] - prices[i - 1];
    11. sum += (val > 0? val: 0);
    12. }
    13. return sum;
    14. }
    15. vector<vector<vector<int>>> dp(k + 1, vector<vector<int>>(prices.size() + 1, vector<int>(2, 0)));
    16. for(int t = 0; t <= k; t++)
    17. dp[t][0][1] = -1000000;
    18. for(int i = 0; i < prices.size(); i++)
    19. dp[0][i][1] = -1000000;
    20. for(int t = 1; t <= k; t++)
    21. {
    22. for(int i = 1; i <= prices.size(); i++)
    23. {
    24. dp[t][i][0] = max(dp[t][i - 1][0], dp[t][i - 1][1] + prices[i - 1]);
    25. dp[t][i][1] = max(dp[t][i - 1][1], dp[t - 1][i - 1][0] - prices[i - 1]);
    26. }
    27. }
    28. return dp[k][prices.size()][0];
    29. }
    30. };

    2>买入后卖出才算一次交易:
    dp[t][0][0] 0天t次交易,手上不持有: 0
    dp[t][0][1] 0天t次交易,手上持有: 不可能(0天没有股票,所以无法买入持有) 【如果这里不这样初始化,而是初始化为0,那么我t次交易的无法去做max,max它会取这个0,而不会去取那些负值】
    dp[0][i][0] i天0次交易,手上不持有:0
    dp[0][i][1] i天0次交易,手上持有:有效的 max(-prices)
    dp[0][i][1] = max(dp[0][i - 1][1], -prices[i])

    class Solution {
    public:
       int maxProfit(int k, vector<int>& prices) {
           if(!prices.size()) return 0;
           if(k >= prices.size()/2)
           {
               int sum = 0;
               for(int i = 1; i < prices.size(); i++)
               {
                   int val = prices[i] - prices[i - 1];
                   sum += (val > 0? val: 0);
               }
               return sum;
           }
           vector<vector<vector<int>>> dp(k + 1, vector<vector<int>>(prices.size() + 1, vector<int>(2, 0)));
           for(int t = 0; t <= k; t++)
           {
               dp[t][0][1] = -1000000;
           }
    
           dp[0][1][1] = -prices[0];
           for(int i = 2; i <= prices.size(); i++)
               dp[0][i][1] = max(dp[0][i - 1][1], -prices[i - 1]);
           for(int t = 1; t <= k; t++)
           {
               for(int i = 1; i <= prices.size(); i++)
               {
                   dp[t][i][0] = max(dp[t][i - 1][0], dp[t - 1][i - 1][1] + prices[i - 1]);
                   dp[t][i][1] = max(dp[t][i - 1][1], dp[t][i - 1][0] - prices[i - 1]);
    
               }
           }
           return dp[k][prices.size()][0];
       }
    };
    

    二维数组的解法
    如果说我们把一次买/一次卖都当是一次交易,那么总的交易数字是2*k,0表示没有交易,0天代表没有股票
    dp[0][0] = 0 0天么有交易,钱最大是0
    dp[t][0] 当是第0天的时候,t(t>=1)次交易,第0天没有交易,所以是-100000
    【这里初始化后,下面这里才是正确的,如果不初始化为-1000000,初始化为0,t = 1 那么这里相当于不会买入dp[t][i] = max(dp[t - 1][i - 1] - prices[i - 1], dp[t][i - 1]) 】

    class Solution {
    public:
       int maxProfit(int k, vector<int>& prices) {
           if(!prices.size()) return 0;
           if(k >= prices.size()/2)
           {
               int sum = 0;
               for(int i = 1; i < prices.size(); i++)
               {
                   int val = prices[i] - prices[i - 1];
                   sum += (val > 0? val: 0);
               }
               return sum;
           }
           vector<vector<int>> dp(k * 2 + 1, vector<int>(prices.size() + 1, 0));
           for(int t = 1; t <= 2 * k; t += 2)
               dp[t][0] = -1000000;
           for(int t = 1; t <= 2 * k; t++)
           {
               for(int i = 1; i <= prices.size(); i++)
               {
                   if(t%2 == 1)//买入
                   {
                       dp[t][i] = max(dp[t - 1][i - 1] - prices[i - 1], dp[t][i - 1]);
                   }
                   else//卖出
                   {
                       dp[t][i] = max(dp[t - 1][i - 1] + prices[i - 1], dp[t][i - 1]);
                   }
               }
           }
           return dp[k * 2][prices.size()];
       }
    };
    

    还有一种思路:
    dp[t][i] i天,最多t次交易完成后,最大利润
    转移方程
    i天,最多t次交易完成后,最大利润 = max(i-1天已经交易了t次, j - 1天已经交易t -1次 + prices[i] - prices[j])

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

    优化之后

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

    一维数组

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

    第二次写题

    class Solution {
    public:
        int maxProfit(int k, vector<int>& prices) {
            if(prices.size() <= k/2)
            {
                int profit = 0;
                for(int i = 1; i < prices.size(); i++)
                    if(prices[i] > prices[i - 1])
                        profit += prices[i] - prices[i - 1];
                return profit;
            }
            //如果买入就算一次交易
            vector<vector<vector<int>>> dp = vector<vector<vector<int>>>(k + 1, vector<vector<int>>(prices.size() + 1, vector<int>(2, 0)));
            for(int i = 0; i <= k; i++)
                dp[i][0][1] = -10000;
            for(int i = 1; i <= prices.size(); i++)
                dp[0][i][1] = -10000;
            for(int i = 1; i <= k; i++)
            {
                for(int j = 1; j <= prices.size(); j++)
                {
                    dp[i][j][0] = max(dp[i][j - 1][0], dp[i][j - 1][1] + prices[j - 1]);
                    dp[i][j][1] = max(dp[i][j - 1][1], dp[i - 1][j - 1][0] - prices[j - 1]);
                }
            }
            return dp[k][prices.size()][0];
        }
    };
    
    class Solution {
    public:
        int maxProfit(int k, vector<int>& prices) {
            if(prices.size() <= k/2)
            {
                int iProfit = 0;
                for(int iDay = 1; iDay < prices.size(); iDay++)
                {
                    if(prices[iDay] > prices[iDay - 1])
                        iProfit += prices[iDay] - prices[iDay - 1];
                }
                return iProfit;
            }
            //买入卖出才算一次交易
            vector<vector<vector<int>>> aProfit = vector<vector<vector<int>>>(k + 1, vector<vector<int>>(prices.size() + 1, vector<int>(2, 0)));
            for(int iTimes = 0; iTimes <= k; iTimes++)
                aProfit[iTimes][0][1] = -100000;
            for(int iDay = 1; iDay <= prices.size(); iDay++)
            {
                aProfit[0][iDay][1] = max(aProfit[0][iDay - 1][1], -prices[iDay - 1]);
                // cout<< iDay << " " << aProfit[0][iDay][1] << endl;
            }
            for(int iTimes = 1; iTimes <= k; iTimes++)
            {
                for(int iDay = 1; iDay <= prices.size(); iDay++)
                {
                    aProfit[iTimes][iDay][0] = max(aProfit[iTimes][iDay - 1][0], aProfit[iTimes - 1][iDay - 1][1] + prices[iDay - 1]);
                    aProfit[iTimes][iDay][1] = max(aProfit[iTimes][iDay - 1][1], aProfit[iTimes][iDay - 1][0] - prices[iDay - 1]);
                }
            }
            return aProfit[k][prices.size()][0];
        }
    };
    

    上面两种写法要注意的是,首先因为两层的Loop是从交易次数等于1开始的,所以交易次数为0的时候就需要先赋值了。为什么交易次数为0的要先赋值,这相当于初始条件。而对于买入算一次交易还是卖出才算一次交易两种定义方式的不同,又会导致初始状态的不同,也就是交易次数为0的时候的状态值的不同。同样是转移,但是转移方程不同。
    让我们来仔细看一下这个转移的方程。

    一次买入或者一次卖出算一次交易

    class Solution {
    public:
        int maxProfit(int k, vector<int>& prices) {
            if(prices.size() <= k/2)
            {
                int iProfit = 0;
                for(int iDay = 1; iDay < prices.size(); iDay++)
                {
                    iProfit += (prices[iDay] > prices[iDay - 1])?(prices[iDay] - prices[iDay - 1]):0;
                }
                return iProfit;
            }
            vector<vector<int>> aProfit = vector<vector<int>>(2 * k + 1, vector<int>(prices.size() + 1, 0));
            for(int iTimes = 1; iTimes <= 2 * k; iTimes += 2)
                aProfit[iTimes][0] = -10000;
            for(int iTimes = 1; iTimes <= 2 * k; iTimes++)
            {
                for(int iDay = 1; iDay <= prices.size(); iDay++)
                {
                    if(iTimes % 2 == 1)//买入
                        aProfit[iTimes][iDay] = max(aProfit[iTimes][iDay - 1], aProfit[iTimes - 1][iDay] - prices[iDay - 1]);
                    else//卖出
                        aProfit[iTimes][iDay] = max(aProfit[iTimes][iDay - 1], aProfit[iTimes - 1][iDay] + prices[iDay - 1]);
                }
            }
            return aProfit[2 * k][prices.size()];
        }
    };
    

    第三次写题

    class Solution {
    public:
        int maxProfit(int k, vector<int>& prices) {
            vector<vector<vector<int>>> aProfit = vector<vector<vector<int>>>(k + 1, vector<vector<int>>(prices.size() + 1, vector<int>(2, 0)));
            if(prices.size() <= k/2)
            {
                int iProfit = 0;
                for(int i = 1; i < prices.size(); i++)
                {
                    if(prices[i - 1] < prices[i])
                        iProfit += (prices[i] - prices[i - 1]);
                }
                return iProfit;
            }
            //买入加卖出是一次交易
            for(int i = 0; i <= k; i++)
                aProfit[i][0][1] = -10000;
    
            for(int i = 1; i <= prices.size(); i++)
                aProfit[0][i][1] = max(aProfit[0][i- 1][1], -prices[i - 1]);
    
            for(int i = 1; i <= k; i++)
            {
                for(int j = 1; j <= prices.size(); j++)
                {
                    aProfit[i][j][0] = max(aProfit[i][j - 1][0], aProfit[i - 1][j - 1][1] + prices[j - 1]);
                    aProfit[i][j][1] = max(aProfit[i][j - 1][1], aProfit[i][j - 1][0] - prices[j - 1]);
                }
            }
            return aProfit[k][prices.size()][0];
        }
    };
    

    image.png
    修改后

    class Solution {
    public:
        int maxProfit(int k, vector<int>& prices) {
            if(prices.size() <= k/2)
            {
                int iProfit = 0;
                for(int i = 1; i < prices.size(); i++)
                {
                    if(prices[i - 1] < prices[i])
                        iProfit += (prices[i] - prices[i - 1]);
                }
                return iProfit;
            }
            vector<vector<vector<int>>> aProfit = vector<vector<vector<int>>>(k + 1, vector<vector<int>>(prices.size() + 1, vector<int>(2, 0)));
            //买入加卖出是一次交易
            for(int i = 0; i <= k; i++)
                aProfit[i][0][1] = -10000;
    
            for(int i = 1; i <= prices.size(); i++)
                aProfit[0][i][1] = max(aProfit[0][i - 1][1], -prices[i - 1]);
    
            for(int i = 1; i <= k; i++)
            {
                for(int j = 1; j <= prices.size(); j++)
                {
                    aProfit[i][j][0] = max(aProfit[i][j - 1][0], aProfit[i - 1][j - 1][1] + prices[j - 1]);
                    aProfit[i][j][1] = max(aProfit[i][j - 1][1], aProfit[i][j - 1][0] - prices[j - 1]);
                }
            }
            return aProfit[k][prices.size()][0];
        }
    };
    

    未标题-1.jpg