动态规划(day11)买卖股票问题进阶-Toy模板网

这篇具有很好参考价值的文章主要介绍了动态规划(day11)买卖股票问题进阶。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

看到题目的第一想法

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

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

188.买卖股票的最佳时机IV

看到题目的第一想法

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

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

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];
    }
}

188.买卖股票的最佳时机IV

力扣题目链接(opens new window)

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

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

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

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

提示：

0 <= k <= 100
0 <= prices.length <= 1000
0 <= prices[i] <= 1000算法公开课

《代码随想录》算法视频公开课 (opens new window)：动态规划来决定最佳时机，至多可以买卖K次！| LeetCode：188.买卖股票最佳时机4 (opens new window)

看到题目的第一想法

按照买卖股票的最佳时机III的思路

上面是要两次，这里是K次

找与上一题相关的规律

dp[i][j] 需要考虑j的取值范围

第i天

K次的话 j的取值范围为 0~2k

0代表没操作

[1，2] 代表第一次买入卖出的最大值，都是取最大

[3,4]代表第二次买入卖出的最大值

[5，6]代表第三次买入卖出的最大值

[7，8] 代表第四次买入卖出的最大值

。。。

[2K-1,2K]代表第K次买入卖出的最大值

遍历时 j从1到2k

若j为奇数代表买入的最大现金

若j为偶数代表卖出的最大现金

初始化时，只有j为奇数需要初始化为-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天买入再卖出再买入

代码随想录中，J遍历时，每次选中的是要赋值的下标的前一个，

然后给dp[i][j+1]和dp[i][j+2]赋值(注意当天不买入的最大值，和买入的最大值的赋值)

注意当天不买入的最大值max(dp[i-1][j+1],dp[i-1][j]-price[i])，

和买入的最大值的赋值max(dp[i-1][j+2],dp[i-1][j]+price[i]);

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

按照正常的分析，就可以解决了

初始化的for循环可能有点冗余，可以直接写成for(i=1;i<2k;i+=2)文章来源地址https://www.toymoban.com/news/detail-812407.html

class Solution {
    public int maxProfit(int k, int[] prices) {
        //我的做法
        //设置一个数组  k次交易依赖k-1次的内容
        //第一次 买入，第一次卖出 的最大现金
        //Math.max(dp[i-1][1],dp[i-1][0]-price[i])
        //Math.max(dp[i-1][2],dp[i-1][1]+price[i]);
        //第二次买入，第二次卖出
        //Math.max(dp[i-1][3],dp[i-1][2]-price[i])
        //Math.max(dp[i-1][4],dp[i-1][3]+price[i])
        //第三次买入，第三次卖出
        //Math.max(dp[i-1][5],dp[i-1][4]-pirce[i])
        //Math.max(dp[i-1][6],dp[i-1][5]+price[i])
        //第k次买入，第k次卖出
        //Math.max(dp[i-1][2k-1],dp[i-1][2k-2]-price[i]);
        //Math.max(dp[i-1][2k],dp[i-1][2k-1]+price[i]);
        //定义dp数组，以及每个下标的含义
        //买入i or 卖出i的最大现金
        //有可能是之前买入，也可能是之前卖出
        //确定递推公式
        //dp数组初始化
        //dp的大小应该为 dp[price.length][]
        //dp[0][0]=0;
        //dp[0][1]=-price;
        //dp[0][2]=0
        //dp[0][3]=-price;
        //..
        //dp[0][2k-1]=-price;
        //dp[0][2k]=0
        //确定遍历顺序
        //举例推导dp数组
        int[][] dp = new int[prices.length][2*k+1];
        dp[0][0]=0;
        for(int i=1;i<2*k;i++){
            dp[0][i]=-prices[0];
            i++;
        }
        /*for(int i=1;i<prices.length;i++){
            for(int j=1;j<=2*k;j++){
                if(j%2==1){
                    //之前买入or当天j/2次买入
                    dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-1]-prices[i]);
                    continue;
                }
                if(j%2==0){
                    //之前卖出or当天卖出
                    dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-1]+prices[i]);
                }
            }
        }*/
        //卡哥做法和我的差不多 ，不过在k遍历那里有点不一样
        for(int i=1;i<prices.length;i++){
            //这里是j<2*k-1 我之前没-1
            for(int j=0;j<2*k-1;j+=2){
                    //之前买入or当天买入
                    //dp[i][j+1]=Math.max(dp[i-1][j+1],dp[i-1][j]-prices[i]);
                    //注意后面也是Math.max(dp[i-1][j+1],dp[i-1][j]-prices[i]);dp[i-1][j+1]
                    dp[i][j+1]=Math.max(dp[i-1][j+1],dp[i-1][j]-prices[i]);
                    dp[i][j+2]=Math.max(dp[i-1][j+2],dp[i-1][j+1]+prices[i]);
            }
        }
        return dp[prices.length-1][2*k];
        


    }
}

到了这里，关于动态规划(day11)买卖股票问题进阶的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！