本文共 1342 字，大约阅读时间需要 4 分钟。

三维状态机dp 可以考虑三维dp，第一维记录天数，第二维记录完成交易数0或者1或者2，第三维记录当前是否持有股票 很重要的一点是第二维记录的是当天可以完成的最大交易数！！并不是当天一定完成了2笔交易的意思。 所以basecase是第一天持有就是-prices[i]，不持有就是0。不管今天最大交易数是几。 状态转移就自己推就行了，最后返回的就是最后一天最多完成2次的不持有股票的情况

class Solution {
   public:    int maxProfit(vector
   
    & prices) {
           //最多完成两笔交易，也可以只完成一笔或者零笔        if(prices.size() <= 1) return 0;        //可以考虑三维dp，第一维记录天数，第二维记录完成交易数0或者1或者2，第三维记录当前是否持有股票        //第二维记录的是最多交易次数，也就是当天的最多交易次数，不是当天交易了几次(非常重要！！)        //如果你记录当天完成的交易次数，那么最后返回的值和状态转移方程都有变化        //0是持有股票，1是不持有股票，在交易出去之后才交易次数+1        vector
    
     
      
       >> dp(prices.size(),vector
       
        
         >(3,vector
         
          (2))); //int res = 0; //basecase: dp[0][0][0] = 0; dp[0][0][1] = -prices[0]; dp[0][1][0] = 0; dp[0][1][1] = -prices[0]; dp[0][2][0] = 0; dp[0][2][1] = -prices[0]; for(int i = 1; i < prices.size(); ++i){ //如果今天不持股且交易次数为0，证明昨天也没持股 dp[i][0][0] = dp[i-1][0][0]; //如果今天持股，交易次数为0，可能昨天就持股了，或者今天刚持股(昨天不持股) dp[i][0][1] = max(dp[i-1][0][1],dp[i-1][0][0]-prices[i]); //如果今天不持股且交易次数为1，可能昨天就不持股，或者今天刚卖 dp[i][1][0] = max(dp[i-1][1][0],dp[i-1][0][1]+prices[i]); //如果今天持股且交易次数为1，可能昨天就持股了，或者今天刚持股 dp[i][1][1] = max(dp[i-1][1][1],dp[i-1][1][0]-prices[i]); //如果今天不持股且交易次数为2，可能昨天就不持股了，或者是今天卖的 dp[i][2][0] = max(dp[i-1][2][0],dp[i-1][1][1]+prices[i]); } //返回的就是最后一天不持股的值且交易2次 return dp[prices.size()-1][2][0]; }};
         
        
       
      
     
    
   

转载地址：http://tvjuk.baihongyu.com/