代码随想录第50天|● 123.买卖股票的最佳时机III ● 188.买卖股票的最佳时机IV

文章目录

• ● 123.买卖股票的最佳时机III
• • 思路
  • 代码一：dp二维数组
  • 代码二：四个数存储
  • ● 188.买卖股票的最佳时机IV
  • • 思路：
    • 代���：

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

      思路

      dp[i][j]中 i表示第i天，j为 [0 - 4] 五个状态，dp[i][j]表示第i天状态j所剩最大现金

      代码一：dp二维数组

      / 版本一class Solution {    public int maxProfit(int[] prices) {        int len = prices.length;        // 边界判断, 题目中 length >= 1, 所以可省去        if (prices.length == 0) return 0;        /*         * 定义 5 种状态:         * 0: 没有操作, 1: 第一次买入, 2: 第一次卖出, 3: 第二次买入, 4: 第二次卖出         */        int[][] dp = new int[len][5];        dp[0][1] = -prices[0];        // 初始化第二次买入的状态是确保 最后结果是最多两次买卖的最大利润        dp[0][3] = -prices[0];        for (int i = 1; i  
      代码二：四个数存储
       
      class Solution {    public int maxProfit(int[] prices) {        /*         * 定义 5 种状态:         * 0: 第一次买入, 1: 第一次卖出, 2: 第二次买入, 3: 第二次卖出         */        int[]dp=new int[4];        dp[0]=-prices[0];        dp[1]=0;        dp[2]=-prices[0];        dp[3]=0;        for(int i=1;i            // 要么保持不变，要么没有就买，有了就卖            dp[0]=Math.max(dp[0],-prices[i]);            dp[1]=Math.max(dp[1],dp[0]+prices[i]);            dp[2]=Math.max(dp[2],dp[1]-prices[i]);            dp[3]=Math.max(dp[3],dp[2]+prices[i]);        }        return dp[3];    }}    public int maxProfit(int k,int[] prices) {        /*         * 定义 5 种状态:         * 0: 第一次买入, 1: 第一次卖出, 2: 第二次买入, 3: 第二次卖出         */        int[]dp=new int[k*2];        for(int i=0;i            if(i%2==0){                dp[i]=-prices[0];            }else{                dp[i]=0;            }        }        for(int i=1;i            // 要么保持不变，要么没有就买，有了就卖            dp[0]=Math.max(dp[0],-prices[i]);            for(int j=1;j                if(j%2==0){                    dp[j]=Math.max(dp[j],dp[j-1]-prices[i]);                }else{                    dp[j]=Math.max(dp[j],dp[j-1]+prices[i]);                }                            }            // dp[0]=Math.max(dp[0],-prices[i]);            // dp[1]=Math.max(dp[1],dp[0]+prices[i]);            // dp[2]=Math.max(dp[2],dp[1]-prices[i]);            // dp[3]=Math.max(dp[3],dp[2]+prices[i]);        }        return dp[2*k-1];    }}