day49【动态规划】买卖股票的最佳时机问题

121.买卖股票的最佳时机：买卖一次

• 题目连接：121.力扣连接

• 讲解连接：代码随想录讲解连接

• 题目描述：给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

  你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

  返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

    示例 1：
    输入：[7,1,5,3,6,4]
    输出：5
    解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
         注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
         
    示例 2：
    输入：prices = [7,6,4,3,1]
    输出：0
    解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10

• 思路：动规五部曲，每天的状态分为两种，一个是当天持有股票的情况下手中的最大现金，一个是当天不持有股票的情况下手中的最大现金。每种状态都由前一天的状态推导而来。

• 代码示例：

class Solution {
    public int maxProfit(int[] prices) {
        //dp[i][0]代表第i天持有股票的最大现金；dp[i][1]代表第i天不持有股票的最大现金；
        int[][] dp = new int[prices.length][2];
        //第1天持有股票的最大现金,和第1天不持有股票的最大现金
        dp[0][0] = -prices[0];
        dp[0][1] = 0;

        for(int i = 1; i < prices.length; i++) {
            //第i天持有股票的最大现金可由两种状态推导出来，其一是第i-1天就持有股票了，其二是第i天才买入股票
            dp[i][0] = Math.max(dp[i-1][0], -prices[i]);
            //同理，第i天不持有股票的最大现金的两种状态，其一是第i-1天就已经不持有股票了，其二是第i天才卖出股票，此时是前一天是持有股票状态，再加上当天卖出股票的钱
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i]);
        }
        //返回到最后一天，不持有股票的最大现金额
        return dp[prices.length-1][1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

122.买卖股票的最佳时机Ⅱ：买卖多次

• 题目连接：122力扣连接

• 讲解连接：代码随想录讲解连接

• 题目描述：给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

  在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

  返回 你能获得的 最大 利润 。

    示例 1：
    输入：prices = [7,1,5,3,6,4]
    输出：7
    解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
         随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
         总利润为 4 + 3 = 7 。
         
    示例 2：
    输入：prices = [1,2,3,4,5]
    输出：4
    解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
         总利润为 4 。
         
    示例 3：
    输入：prices = [7,6,4,3,1]
    输出：0
    解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17

• 贪心思路：计算每天最大利润值，这个方法更简单，但只针对比较特定的场景。

class Solution {
    public int maxProfit(int[] prices) {
        int res = 0;
        int dayprice = 0;
        for(int i = 1; i < prices.length; i++) {
            //计算每天买卖的差额，如果差额是大于0的话，那就对最后的盈利是正向影响。结果就加上当天的利润。
            dayprice = prices[i] - prices[i-1];
            
            if(dayprice > 0) {
                res += dayprice;
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

• 动态规划思路：和上一题很像，唯一不同的是第i天持有股票的最大现金那里，如果第i-1天不持有，第i天才买入的话，此时第i-1天手中的钱不是0了，因为可以多次买卖股票，所以第i-1天的时候手里可能已经有之前盈利的钱，所以此时要用第i-1天不持有股票的钱减去第i天买入股票的钱。

class Solution {
    public int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length][2];

        //初始化,第1天持有股票和不持有股票
        dp[0][0] = -prices[0];
        dp[0][1] = 0;

        for(int i = 1; i < prices.length; i++) {
            //第i天持有股票的最大现金:第i-1天就持有；第i-1天不持有，第i天买入
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]-prices[i]);
            //第i天不持有股票的最大现金：第i-1天就不持有，第i-1天持有，第i天卖出
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0]+prices[i]);
        }
        return dp[prices.length-1][1];

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

123.买卖股票的最佳时机Ⅲ：最多买卖2次

• 题目连接：力扣链接

• 讲解链接：代码随想录讲解链接

• 题意：给定一个数组，它的第 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
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21

• 思路：有两次买卖的机会，状态数增加。有5种状态，对应分析即可。

class Solution {
    public int maxProfit(int[] prices) {
        //dp[i][j],j代表第i天的5种状态。
        int[][] dp = new int[prices.length][5];
        //0代表没有操作
        dp[0][0] = 0;
        //1代表第一次持有股票
        dp[0][1] = -prices[0];
        //2代表第一次不持有股票，初始化时相当于当天买入当天卖出
        dp[0][2] = 0;
        //3代表第二次持有股票，初始化时相当于当天买入卖出一次后又买入
        dp[0][3] = -prices[0];
        //4代表第二次不持有股票
        dp[0][4] = 0;

        for(int i = 1; i < prices.length; i++) {
            dp[i][1] = Math.max(dp[i-1][1], -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];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

188.买卖股票的最佳时机Ⅳ：最多买卖k次

• 题目链接：力扣链接

• 讲解链接：代码随想录讲解

• 题意：给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。

  设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 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 。
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10

• 思路：此题可以自由买卖，买卖k次，根据Ⅲ可发现规律，当状态为奇数时是持有状态，状态为偶数时是不持有状态。

class Solution {
    public int maxProfit(int k, int[] prices) {
        //一次交易有2种状态，加一个0状态，共2*k+1种状态
        int[][] dp = new int[prices.length][k*2+1];
        //初始化状态0：无操作，或初始化偶数状态不持有股票时，初始值都为0，故不用特地初始化。
        dp[0][0] = 0;
        //初始化奇数：持有股票状态
        for(int i = 1; i < k*2; i+=2) {
            dp[0][i] = -prices[0];
        }

        for(int i = 1; i < prices.length; i++){
            for(int j = 0; j < k*2-1; j+=2) {
                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][k*2];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

309.最佳买卖股票时机含冷冻期

• 题目链接：力扣链接

• 讲解链接：代码随想录讲解链接

• 题意：给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。​

  设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

  卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
  注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

    示例 1:
    输入: prices = [1,2,3,0,2]
    输出: 3 
    解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
    
    示例 2:
    输入: prices = [1]
    输出: 0
  1
  2
  3
  4
  5
  6
  7
  8

• 思路：多增加了一个冷冻期，dp数组的状态发生改变。0代表持有股票，1代表保持卖出股票（即冷冻期后是已经卖出股票的状态），2代表卖出股票的状态。原来的状态是持有和不持有，不持有即包含了此题中的保持卖出股票状态和卖出状态两种状态（一种是已经卖出的状态，一种是操作卖出行为的状态）。因为此题多了冷冻期，冷冻期的前一天一定是有卖出行为的状态。3代表冷冻期状态。

class Solution {
    public int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length][4];
        //0:持有股票，1：股票已经卖出状态，2：股票当天卖出状态，3：冷冻期
        dp[0][0] = -prices[0];
        //初始化时状态是非法的，就从递推公式中看需要把状态初始化为多少。
        dp[0][1] = 0;
        dp[0][2] = 0;
        dp[0][3] = 0;
        for(int i = 1; i < prices.length; i++) {
            //持有股票状态：前一天持有/冷冻期的下一天买入/前一天是保持股票卖出状态
            dp[i][0] = Math.max(dp[i-1][0], Math.max(dp[i-1][3]-prices[i], dp[i-1][1]-prices[i]));
            //保持卖出股票状态：前一天是冷冻期（冷冻期已经卖出股票）/前一天已经卖出股票
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][3]);
            //股票当天卖出，前一天是持有股票状态
            dp[i][2] = dp[i-1][0]+prices[i];
            //当天是冷冻期，前一天是卖出操作状态
            dp[i][3] = dp[i-1][2];
        }
        return Math.max(dp[prices.length-1][1], Math.max(dp[prices.length-1][2], dp[prices.length-1][3]));
         
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

714.买卖股票的最佳时机含手续费

• 题目链接：力扣链接

• 讲解链接：代码随想录讲解

• 题意：给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。

  你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

  返回获得利润的最大值。

  注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

    示例 1：
    输入：prices = [1, 3, 2, 8, 4, 9], fee = 2
    输出：8
    解释：能够达到的最大利润:  
    在此处买入 prices[0] = 1
    在此处卖出 prices[3] = 8
    在此处买入 prices[4] = 4
    在此处卖出 prices[5] = 9
    总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8
    
    示例 2：
    输入：prices = [1,3,7,5,10,3], fee = 3
    输出：6
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13

• 思路：和Ⅱ相似，只是在买入/卖出时减去手续费即可。

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int[][] dp = new int[prices.length][2];
        dp[0][0] = -prices[0]-fee;
        dp[0][1] = 0;
        for(int i = 1; i < prices.length; i++) {
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]-prices[i]-fee);
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0]+prices[i]);
        }
        return dp[prices.length-1][1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12