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

时间：2024-02-17 20:29:25

动态规划解法思路：

1.先声明一个二维dp数组来记录每一个下标的的状态，例如：没有买一次操作，买了第一次操作，卖了第一次没买第二次操作，买第二次操作，卖了第二次操作。

2.初始化dp数组的dp【0】【1】=-prices【0】和dp【0】【3】=-prices【0】。再用for循环来进行遍历全部的dp数组，递推公式： dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);

 dp[i][2]=Math.max(dp[i-1][2],dp[i-1][1]+prices[i]);   

   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]);最后返回最后一个下标的两次全部交易的dp数组dp【length-1】【4】，表示整个dp数组中两次交易全部完成的最大利润。

class Solution {
    public int maxProfit(int[] prices) {
        //声明一个dp数组来表示股票每个过程的状态，有没有买一次的操作，买了第一次的操作，卖了第一次后没买第二次的操作，卖了第一次卖了第二次的操作，卖了第二次的操作
        int [][] dp=new int[prices.length][5];
        //买了第一次的操作
        dp[0][1]=-prices[0];
        //卖了第一次卖了第二次的操作
        dp[0][3]=-prices[0];
     for(int i=1;i<prices.length;i++){
          //递推公式，推导每一个下标买了第一次的操作的最大利润
            dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
          //推导每一个下标卖了第一次后没买第二次的操作的最大利润
            dp[i][2]=Math.max(dp[i-1][2],dp[i-1][1]+prices[i]);
          //推导每一个下标卖了第一次买了第二次的操作的最大利润
            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];


    }
}

相关文章