力扣刷题记录114.1-----123. 买卖股票的最佳时机 III(动态规划)

---

一、题目

二、代码

class Solution 
{
public:
    //0表示没有操作
    //1表示第一次持有   (买入)
    //2表示第一次未持有 (卖出)
    //3表示第二次持有   (买入)
    //4表示第三次未持有 (卖出)
    int maxProfit(vector<int>& prices) 
    {
       int i,j;
       int return_int=0;
       int len=prices.size();
       if(len==1)  return 0;
       else
       {
           vector<vector<int>> dp(len,vector<int>(5,0));
           dp[0][0]=0;
           dp[0][1]=-prices[0];
           dp[0][2]=0;
           dp[0][3]=-prices[0];
           dp[0][4]=0;
 
           for(i=1;i<prices.size();i++)
           {
              dp[i][0]=dp[i-1][0];
              dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]);
              dp[i][2]=max(dp[i-1][2],dp[i-1][1]+prices[i]);
              dp[i][3]=max(dp[i-1][3],dp[i-1][2]-prices[i]);
              dp[i][4]=max(dp[i-1][4],dp[i-1][3]+prices[i]); 
           }
           return_int=dp[prices.size()-1][4];
       }
       return return_int;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

三、运行结果