• 代码随想录刷题|LeetCode 123.买卖股票的最佳时机III 188.买卖股票的最佳时机IV

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

    题目链接：力扣

    思路

            这道题目确实情况更加的复杂，但是原理其实和前面的买入股票的题目都是差不多的，数组上的元素代表的就是手中钱的最大值，然后推算出各种情况的最大值，最后可以得到获得利润的最大值

            最多买卖两次，这意味着可以买卖一次，也可以买卖两次，也可以不买卖

    1、确定dp数组以及下标含义

     对股票来说，一天可能有五种状态：

    • 没有操作
    • 第一次买入
    • 第一次卖出
    • 第二次买入
    • 第二次卖出

    i 表示天数，在第几天，j 为（0，4）五种状态，dp[i][j] 代表：第 i 天状态 j 手中的最大现金数

    2、确定递推公式

    dp[i][0] 代表没有操作，所以是从 dp[i - 1][0] 中推导而来

    dp[i][1] 代表第一次买入，可以由两种状态推导而来
            如果第 i 天没有操作 ，那么就是前面的状态，dp[i][1] = dp[i - 1][1]
            如果第 i 天买入股票了，那么dp[i][1] = dp[i-1][0] - prices[i]
            选择其中现金数最大的状态，dp[i][1] = max(dp[i-1][0] - prices[i], dp[i - 1][1])

    dp[i][2] 代表第一次卖出，可以由两种状态推导而来
            如果第 i 天没有操作，那么就是前面的状态，dp[i][2] = dp[i - 1][2]
            如果第 i 天卖出股票了，那么dp[i][2] = dp[i - 1][1] + prices[i]
            选择其中现金数最大的状态，dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])

    dp[i][3] 代表第二次买入，可以由两种状态推导而来
            如果第 i 天没有操作，那么就是前面的状态，dp[i][3] = dp[i - 1][3]
            如果第 i 天买入股票了，那么dp[i][3] = dp[i - 1][2] - prices[i]
            选择其中现金数最大的状态，dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i])

    dp[i][4]代表第二次卖出，可以由两种状态推导而来
            如果第 i 天没有操作，那么就是前面的状态，dp[i][4] = dp[i - 1][4]
            如果第 i 天卖出股票了，那么dp[i][4] = dp[i - 1][3] + prices[i]
            选择其中现金数最大的状态，dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i])

    3、初始化dp数组

            从递推公式可以看出，都是由dp[i-1][0-4]的状态推导而来的，所以 dp[0][0]、dp[0][1]、dp[0][2]、dp[0][3]、dp[0][4] 都需要进行初始化

    第 0 天，没有操作的的话，手中的现金就是0，即 dp[0][0] = 0;

    第 0 天，第一次买入的话，手中的现金就是0 - prices[0]，即 dp[0][1] = -prices[0];

    第 0 天，第一次卖出的话，没有可卖出的，手中的现金就是0，即dp[0][2] = 0;

    第 0 天，第二次买入的话，手中的现金就是0 - prices[0]，即dp[0][3] = -prices[0];

    第 0 天，第二次卖出的话，没有可卖出的，手中的现金就是0，即dp[0][4] = 0;

    4、遍历顺序

            从前向后遍历

    买卖股票的最佳时机|||

    使用二维数组进行推导

    1. class Solution {
    2.     public int maxProfit(int[] prices) {
    3.  
    4.         // 创建dp数组
    5.         int[][] dp = new int[prices.length][5];
    6.  
    7.         // 初始化dp数组
    8.         dp[0][1] = -prices[0];
    9.         dp[0][3] = -prices[0];
    10.  
    11.         // 推导dp数组
    12.         for (int i = 1; i < prices.length; i++) {
    13.             dp[i][0] = dp[i - 1][0];
    14.             dp[i][1] = Math.max(dp[i - 1][1],dp[i - 1][0] - prices[i]);
    15.             dp[i][2] = Math.max(dp[i - 1][2],dp[i - 1][1] + prices[i]);
    16.             dp[i][3] = Math.max(dp[i - 1][3],dp[i - 1][2] - prices[i]);
    17.             dp[i][4] = Math.max(dp[i - 1][4],dp[i - 1][3] + prices[i]);
    18.         }
    19.  
    20.         return dp[prices.length - 1][4];
    21.     }
    22. }

    使用一维数组进行推导

    1. class Solution {
    2.     public int maxProfit(int[] prices) {
    3.  
    4.         // 创建dp数组
    5.         int[] dp = new int[5];
    6.  
    7.         // 初始化dp数组
    8.         dp[1] = -prices[0];
    9.         dp[3] = -prices[0];
    10.  
    11.         // 推导dp数组
    12.         for (int i = 1; i < prices.length; i++) {
    13.             dp[1] = Math.max(dp[1],dp[0] - prices[i]);
    14.             dp[2] = Math.max(dp[2],dp[1] + prices[i]);
    15.             dp[3] = Math.max(dp[3],dp[2] - prices[i]);
    16.             dp[4] = Math.max(dp[4],dp[3] + prices[i]);
    17.         }
    18.  
    19.         return dp[4];
    20.     }
    21. }

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

    题目链接：力扣

    思路

            这道题目其实是上一道题目的进阶版，将最多可买卖两次，进阶成最多可买卖k次，其实就是找到上道题目的规律，运用到这道题目中

    对二维数组来说

    • 首先，就是创建dp数组 
        1. // 最多买卖两次
        2. // 创建dp数组
        3. int[][] dp = new int[prices.length][5];
        4.  
        5. // 最多买卖k次
        6. // 创建dp数组
        7. int[][] dp = new int[prices.length][2*k + 1];
    • 其次就是初始化数组 
        1. // 最多买卖2次
        2. // 初始化dp数组
        3. dp[1] = -prices[0];
        4. dp[3] = -prices[0];
        5.  
        6. // 最多买卖k次
        7. // 初始化dp数组
        8. for (int i = 1; i < 2*k; i += 2) {
        9.    dp[0][i] = -prices[0];
        10. }
    • 最后就是递推阶段 
        1. // 最多买卖2次
        2. // 推导dp数组
        3. for (int i = 1; i < prices.length; i++) {
        4.    dp[i][0] = dp[i - 1][0];
        5.    dp[i][1] = Math.max(dp[i - 1][1],dp[i - 1][0] - prices[i]);
        6.    dp[i][2] = Math.max(dp[i - 1][2],dp[i - 1][1] + prices[i]);
        7.    dp[i][3] = Math.max(dp[i - 1][3],dp[i - 1][2] - prices[i]);
        8.    dp[i][4] = Math.max(dp[i - 1][4],dp[i - 1][3] + prices[i]);
        9. }
        10.  
        11. // 最多买卖k次
        12. // 推导dp数组
        13. for (int i = 1; i < len; i++) {
        14.     for (int j = 0; j < 2*k - 1; j+=2) {
        15.         dp[i][j + 1] = Math.max(dp[i - 1][j + 1],dp[i - 1][j] - prices[i]);
        16.         dp[i][j + 2] = Math.max(dp[i - 1][j + 2],dp[i - 1][j + 1] + prices[i]);
        17.     }
        18. }

    买卖股票的最佳时机IV

    使用二维dp数组进行推导

    1. class Solution {
    2.     public int maxProfit(int k, int[] prices) {
    3.  
    4.         if (k == 0 || prices.length == 0) {
    5.             return 0;
    6.         }
    7.  
    8.         // 创建dp数组
    9.         int len = prices.length;
    10.         int[][] dp = new int[len][2*k + 1];
    11.  
    12.         // 初始化dp数组
    13.         for (int i = 1; i < 2*k; i += 2) {
    14.             dp[0][i] = -prices[0];
    15.         }
    16.  
    17.         // 推导dp数组
    18.         for (int i = 1; i < len; i++) {
    19.             for (int j = 0; j < 2*k - 1; j+=2) {
    20.                 dp[i][j + 1] = Math.max(dp[i - 1][j + 1],dp[i - 1][j] - prices[i]);
    21.                 dp[i][j + 2] = Math.max(dp[i - 1][j + 2],dp[i - 1][j + 1] + prices[i]);
    22.             }
    23.         }
    24.  
    25.         return dp[len-1][2*k];
    26.     }
    27. }

    使用一维dp数组进行推导

    1. class Solution {
    2.     public int maxProfit(int k, int[] prices) {
    3.  
    4.         if (k == 0 || prices.length == 0) {
    5.             return 0;
    6.         }
    7.  
    8.         // 创建dp数组
    9.         int[] dp = new int[2 * k + 1];
    10.  
    11.         // 初始化dp数组
    12.         for (int i = 1; i < 2*k + 1; i+=2) {
    13.             dp[i] = -prices[0];
    14.         }
    15.  
    16.         // 推导dp数组
    17.         for (int i = 1; i < prices.length; i++) {
    18.             for (int j = 0; j < 2*k - 1; j+=2) {
    19.                 dp[j + 1] = Math.max(dp[j + 1],dp[j]-prices[i]);
    20.                 dp[j + 2] = Math.max(dp[j + 2],dp[j+1]+prices[i]);
    21.             }
    22.         }
    23.  
    24.         return dp[2*k];
    25.     }
    26. }

  • 相关阅读:
    [点云分割] 圆柱体分割
    应届女生美团 Java 岗 4 面，一次性斩 offfer，我受到了万点暴击
    [ACTF2020 新生赛]Exec
    利用Promise优化Vue异步操作的方法
    Unity 安卓（Android）端AVProVideo插件播放不了视频，屏幕一闪一闪的
    LabVIEW开发教学实验室自动化INL和DNL测试系统
    聊聊Mybatis的Executor之模板方法模式
    ​python合并列表 青少年编程电子学会python编程等级考试三级真题解析2020年9月
    多媒体操作流程
    （22）STM32——RTC时钟笔记（基于正点原子探索者）
  • 原文地址：https://blog.csdn.net/m0_62575233/article/details/128115895