动态规划(day11)买卖股票问题进阶(尚未写完)

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

力扣题目链接(opens new window)

给定一个数组，它的第 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

看到题目的第一想法
? ? ? ? ? ? ? ?

? ? ? ? 可以购买两次该怎么做？

? ? ? ? 回忆之前的?购买一次

? ? ? ? 第一题，购买一次的最大值

? ? ? ? 第二题：购买卖出多次的最大值

? ? ? ? dp[i][0] 第i天股票买入的最大金额

? ? ? ? ? ? ? ? ? ? ? ? 之前就买入

? ? ? ? ? ? ? ? ? ? ? ? 当天买入Max(dp[i-1][0],dp[i-1][1]-price[i])

???????? dp[i][1]? 股票卖出的最大金额

? ? ? ? ? ? ? ? ? ? ? ? 之前就买入

? ? ? ? ? ? ? ? ? ? ? ? 当天买入Max(dp[i-1][1],dp[i-1][0]+price[i])

????????

看到代码随想录之后的想法

? ? ? ? ? ? ? ? 如果是两次，需要记录两次的买入和卖出的最大值

? ? ? ? ? ? ? ? 如何记录？

? ? ? ? ? ? ? ? 利用二维数组：

??????????????dp[i][0]? ? ? ? ?第i天不进行任何操作

? ? ? ? ? ? ? dp[i][1]? ? ? ? ?第i天or之前买入的最大金额 Math.max(dp[i-1][0]-price[i],dp[i-1][1]);

? ? ? ? ? ? ? dp[i][2]? ? ? ? ?第i天or之前卖出的最大金额 Math.max(dp[i-1][1]+price[i],dp[i-1][1]);

? ? ? ? ? ? ? dp[i][3]? ? ? ? ?第i天第二次买入or之前买入的最大金额

????????????????????????????????????????Math.max(dp[i-1][2]-price[i],dp[i-1][3]);

? ? ? ? ? ? ? dp[i][4]? ? ? ? ?第i天第二次卖出or之前卖出的最大金额

????????????????????????????????????????Math.max(dp[i-1][3]+price[i],dp[i-1][4]);

? ? ? ? 初始化的对应值：

? ? ? ? dp[0][1]:-price[0] 第1天买入

? ? ? ? dp[0][2]:0 第1天买入再卖出

????????dp[0][3]：-price[0] 第1天买入再卖出再买入

? ? ? ? dp[0][4]：0 第1天买入再卖出再买入

自己实现过程中遇到的困难

? ? ? ? return dp[prices.length-1][4]? 返回最后一天的第二次卖出的最大现金

class Solution {
    public int maxProfit(int[] prices) {
        //可以买入两笔交易
        //我的思路，按照之前的做法。二维数组
        //dp[prices.length][2] 
        // dp[i][0] 买入股票的最大现金
        // dp[i][1] 卖出股票的最大现金
        //卡哥思路 
        //dp数组的定义与下标的含义
        //dp[prices.length][5]
        //dp[i][0] 不操作
        //dp[i][1] 第一次买入后的最大现金
        // 之前就买入 or 当天买入
        // Math.max(dp[i-1][1],dp[i][0]-prices[i]);
        //dp[i][2] 第一次卖出后的最大现金
        // 之前就卖出 or 当天卖出
        // Math.max(dp[i-1][2],dp[i-1][1]+price[i])
        //dp[i][3] 第二次买入后的最大现金
        // Math.max(dp[i-1][3],dp[i-1][2]-price[i]);
        // 之前就买入 or 当天买入
        //dp[i][4] 第二次卖出后的最大现金
        // 之前就卖出 or 当天卖出
        // Math.max(dp[i-1][4],dp[i-1][3]+price[i]);
        //确定递推公式
        //dp数组初始化
        //dp[0][0]=0
        //dp[0][1]=-price[0]
        //dp[0][2]=0
        //dp[0][3]=-price[0]
        //dp[0][4]=0
        //确定遍历顺序
        //从前往后
        int[][] dp = new int[prices.length][5];
        //dp[i][0]代表不做任何操作的最大现金
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        dp[0][2] = 0;
        //相当于第一天买入又卖出又买入
        dp[0][3] = -prices[0];
        //相当于第一天买入又卖出，又买入又卖出
        dp[0][4] = 0;
        //0已经初始化要从1开始
        for(int i=1;i<prices.length;i++){
            //之前买入 or 这一次买入
            dp[i][1] = Math.max(dp[i-1][1],dp[i][0]-prices[i]);
            //之前卖出 or 这一次卖出 ，在这一次买入dp[i][0]的基础上考虑
            dp[i][2] = Math.max(dp[i-1][2],dp[i-1][1]+prices[i]);
            //第二次则是在第一次dp[i-1][2]卖出的现金的基础上考虑
            dp[i][3] = Math.max(dp[i-1][3],dp[i-1][2]-prices[i]); 
            dp[i][4] = Math.max(dp[i-1][4],dp[i-1][3]+prices[i]);  
        }
        return dp[prices.length-1][4];
    }
}