数学|动态规划LeetCode-123.买卖股票的最佳时机3

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

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

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

示例 1:

输入：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：

输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。   
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。   
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3：

输入：prices = [7,6,4,3,1] 
输出：0 
解释：在这个情况下, 没有交易完成, 所以最大利润为 0。

示例 4：

输入：prices = [1]
输出：0

提示：

1 <= prices.length <= 10^5
0 <= prices[i] <= 10^5

这题是个系列题，我们得从买卖股票的最佳时机1开始做起，从1开始做所定义的dp含义都是相似的。不懂写买卖股票的最佳时机1和2的小伙伴，可以看我的分享的博客。
动态规划LeetCode-121.买卖股票的最佳时机1-CSDN博客
 动态规划LeetCode-122.买卖股票的最佳时机2-CSDN博客

那我们现在开始看一下这三个有什么区别。买卖股票的最佳时机1是只可以买卖一次，2是可以买卖无限次，而3是只可以买卖至多两次。之前的1和2的dp含义dp[i][0] 表示第i天持有股票时的最大现金，dp[i][1] 表示第i天不持有股票时的最大现金，我们记录每天持有和不持有的最大现金，慢慢推导到最后就可以得出卖出得到的最大现金。
那现在买卖股票的最佳时机3说至多2次，那我们就得细分状态。一天就五个状态，无操作、第一次买入、第一次卖出、第二次买入、第二次卖出，我们在每天分别记录进行这些操作手上所得到的最大现金

所以我们就得出dp含义：
dp[i][0]：表示第i天无操作得到手上最大现金。
dp[i][1]：表示第i天第一次持有股票时手上的最大现金。
dp[i][2]：表示第i天第一次不持有股票时手上的最大现金。
dp[i][3]：表示第i天第二次持有股票时手上的最大现金。
dp[i][4]：表示第i天第二次不持有股票时手上的最大现金。

注意，我们依旧解释一下持有和不持有，持有和不持有不一定是真正的买入，我们只是记录记录！也可以这么理解一下，比如dp[i][1]，第i天，如果（注意是如果）这时候进行第一次买入，那我们手上的最大现金是多少，每天都进行比较和记录最值，第i天如果进行第一次买入股票，这时手上的最大现金是多少，一直记录着最值慢慢推导到最后，所以dp[pricesSize-1][1]所得到的值就是真正的第一次买入股票时手上的最大现金。因为是第一次买入，最后的dp[pricesSize-1][1]的dp值就是真正第一次买入股票时股票的价格，真正第一次买入的时候是在股票最低价格的时候买，dp对应的就是手上的最大现金。我们每天都把这些操作记录下来，相当于是第i天如果进行某个操作手上的最大现金，每次都保存符合题意的最值，一直记录并推导到最后就得出结果。

所以我们看一下递推公式：
dp[i][0]：无操作的话我们初始化第0天之后，以后的第i天dp[i][0]延续第i-1天的dp[i-1][0]。dp[i][0] = dp[i-1][0];

dp[i][1]：还未进行第一次买入的时候，我们手上的现金为0，那如果我们要是进行第一次买入，那就是无操作所得的最大现金dp[i][0]减去prices[i]得到第i天第一次持有股票时手上的最大现金，这个与第i-1天的dp[i][1]进行比较取最大值，每天记录保存的是第一次持有股票时手上的最大现金。 dp[i][1] = dp[i-1][1] > dp[i-1][0] - prices[i] ? dp[i-1][1] : dp[i-1][0] - prices[i];

dp[i][2]：第一次不持有的话肯定是在第一次持有的情况下进行的，所以就是第一次持有股票的最大现金加上prices[i]（当前不持有则是卖出，那就是获得当前价格的金额）。 dp[i][2] = dp[i-1][2] > dp[i-1][1] + prices[i] ? dp[i-1][2] : dp[i-1][1] + prices[i];

dp[i][3]：同理，第二次持有是在第一次不持有的情况下进行的，所以就是第一不持有股票时的最大现金减去prices[i](持有的话就是买入了，那手上最大现金就是减去prices[i]，但不是真正的买入，只是一个如果并记录)。dp[i][3] = dp[i-1][3] > dp[i-1][2] - prices[i] ?dp[i-1][3] : dp[i-1][2] - prices[i];

dp[i][4]：同理，dp[i][4] = dp[i-1][4] > dp[i-1][3] + prices[i] ? dp[i-1][4] : dp[i-1][3] + prices[i];

初始化：
dp[i][0]：第0天，不进行操作，手上最大现金就是0，所以dp[0][0] = 0;

dp[i][1]：第0天，如果进行第一次持有（买入但并不是真正的买入），手上的最大现金就是0-prices[0],所以dp[0][1] = 0-prices[0];

dp[i][2]：第0天，如果进行第一次不持有,手上的最大现金就是0 - prices[0] + prices[0]=0,所以dp[0][2] = 0;

dp[i][3]：第0天，如果进行第二次持有，手上的最大现金就是0 - prices[0] + prices[0] - prices[0]= 0-prices[0]，所以dp[0][3] = 0-prices[0];

dp[i][4]：第0天，如果进行第二次不持有，手上的最大现金就是0 - prices[0] + prices[0] - prices[0] + prices[0] = 0，所以dp[0][4] = 0;

遍历顺序：从前往后

打印数组：当遇到疑惑或者提交错误时，打印数组出来比较快速的看看哪一步有错。

以下是我在力扣c语言提交的代码，仅供参考：


int maxProfit(int* prices, int pricesSize) {
    //五个操作
    int dp[pricesSize][5];
 
    //初始化
    dp[0][0] = 0;
    dp[0][1] = 0-prices[0];
    dp[0][2] = 0;
    dp[0][3] = 0-prices[0];
    dp[0][4] = 0;
 
    for(int i = 1;i<pricesSize;i++)
    {
 
        dp[i][0] = dp[i-1][0];
        
        // 第一次持有：保持现状（第i-1天的结果）或当天买入
        dp[i][1] = dp[i-1][1] > dp[i-1][0] - prices[i] ? dp[i-1][1] : dp[i-1][0] - prices[i];
        
        // 第一次不持有：保持现状（第i-1天的结果）或当天卖出
        dp[i][2] = dp[i-1][2] > dp[i-1][1] + prices[i] ? dp[i-1][2] : dp[i-1][1] + prices[i];
 
        // 第二次持有：保持现状（第i-1天的结果）或第一次卖出后买入
        dp[i][3] = dp[i-1][3] > dp[i-1][2] - prices[i] ?dp[i-1][3] : dp[i-1][2] - prices[i];
 
         第二次不持有：保持现状（第i-1天的结果）或第二次买入后卖出
        dp[i][4] = dp[i-1][4] > dp[i-1][3] + prices[i] ? dp[i-1][4] : dp[i-1][3] + prices[i];
    }
 
    return dp[pricesSize-1][4];
}

评论记录：