LeetCode 123 买卖股票的最佳时机III

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例：

输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天（股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

对于交易的次数进行了限制，最多只能进行两次交易，也就是交易次数<=2。

动态规划

注：此处不能使用贪心进行求解，贪心的思想为：在给定的价格数组中，寻找单调增区间，选取两个区间宽度最大的单调增区间，两个区间的宽度的相加就是最大利润，也可能不存在这样的两个或一个区间。但是对于数组 [1,2,4,2,5,7,2,4,9,0] ，此时贪心求解的值为12，但实际的最大利润为13。

基于动态规划实现：重点依旧是动态规划数组的定义和推导。（此处的定义，使用的是持有，也就是不关系具体是在那一天进行买卖，也就是关心的是在某一天是否拥有股票）

动态规划数组得到定义：定义数组 dp[n][5] ，那么数组的含义为：

dp[i][0] 表示在第 i 天不对股票进行操作所拥有的最大现金数
dp[i][1] 表示在第 i 天第一次持有股票所拥有的最大现金数
dp[i][2] 表示在第 i 天第一次不持有股票所拥有的最大现金数
dp[i][3] 表示在第 i 天第二次持有股票所拥有的最大现金数
dp[i][4] 表示在第 i 天第二次不持有股票所拥有的最大现金数

动态规划数组的推导：在第 i 天需要对5个状态进行推导。

dp[i][0]=0
dp[i][1] 此处有两种情况：第一，是在第 i 天买入的 =dp[i-1][0]-prices[i] ，第二是在之前买入的 =dp[i-1][1] ，所以 dp[i][1]=max(dp[i-1][0]-prices[i],dp[i-1][1])
dp[i][2] 也有两种情况：第一，是在第 i 天卖出的 =dp[i-1][1]+prices[i] ，第二是在之前卖出的 =dp[i-1][2] ，所以 dp[i][2]=max(dp[i-1][1]+prices[i],dp[i-1][2])
dp[i][3] 此处有两种情况：第一，是在第 i 天买入的 =dp[i-1][2]-prices[i] ，第二是在之前买入的 =dp[i-1][3] ，所以 dp[i][3]=max(dp[i-1][2]-prices[i],dp[i-1][3])
dp[i][2] 也有两种情况：第一，是在第 i 天卖出的 =dp[i-1][3]+prices[i] ，第二是在之前卖出的 =dp[i-1][4] ，所以 dp[i][4]=max(dp[i-1][3]+prices[i],dp[i-1][4])

动态规划数组的初始化：此处主要是对第 0 天进行初始化，不操作 dp[0][0]=0 ，那么在第 0 天第一次持有 dp[0][1]=-prices[0] 在第 0 天第一次不持有，本质上就是买入后当天卖出 dp[0][2]=0 ，那么同理第二次持有和不持有的情形，也是当天买入后，当天卖出 dp[0][3]=-prices[0],dp[0][4]=0
动态规划数组的遍历：从前向后遍历的方式
举例验证：对于数组 prices = [3,3,5,0,0,3,1,4] ，对应的动态规划数组为：

0 ,-3 , 0 ,-3 , 0 ,
0 ,-3 , 0 ,-3 , 0 ,
0 ,-3 , 2 ,-3 , 2 ,
0 , 0 , 2 , 2 , 2 ,
0 , 0 , 2 , 2 , 2 ,
0 , 0 , 3 , 2 , 5 ,
0 , 0 , 3 , 2 , 5 ,
0 , 0 , 4 , 2 , 6 ,

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        if(n==1) return 0;
        vector<vector<int>> dp(n,vector<int>(5,0));
        dp[0][1]-=prices[0];
        dp[0][3]-=prices[0];
        for(int i=1;i<n;i++){
            dp[i][1]=max(dp[i-1][0]-prices[i],dp[i-1][1]);
            dp[i][2]=max(dp[i-1][1]+prices[i],dp[i-1][2]);
            dp[i][3]=max(dp[i-1][2]-prices[i],dp[i-1][3]);
            dp[i][4]=max(dp[i-1][3]+prices[i],dp[i-1][4]);
        }
        return max(dp[n-1][0],max(dp[n-1][2],dp[n-1][4]));
    }
};

此处也是只使用了前一天的数据，可以使用滚动数组优化：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        if(n==1) return 0;
        vector<vector<int>> dp(2,vector<int>(5,0));
        dp[0][1]-=prices[0];
        dp[0][3]-=prices[0];
        for(int i=1;i<n;i++){
            dp[1][1]=max(dp[0][0]-prices[i],dp[0][1]);
            dp[1][2]=max(dp[0][1]+prices[i],dp[0][2]);
            dp[1][3]=max(dp[0][2]-prices[i],dp[0][3]);
            dp[1][4]=max(dp[0][3]+prices[i],dp[0][4]);
            dp[0]=dp[1];
        }
        return max(dp[1][0],max(dp[1][2],dp[1][4]));
    }
};

Mark's blogs

LeetCode-123-买卖股票的最佳时机III

LeetCode 123 买卖股票的最佳时机III

动态规划