【力扣刷题】Day30——DP专题

六、股票买卖系列

---

上一篇文章：【力扣刷题】Day29——DP专题_塔塔开!!!的博客-CSDN博客

23. 买卖股票的最佳时机

题目链接：121. 买卖股票的最佳时机 - 力扣（LeetCode）

Code

思路一：贪心

买入的时候股票的金额越小越好，固定左边的最小值，枚举右边若不断计算更新即可。

class Solution {
    int minPrice = 0x3f3f3f3f;
    public int maxProfit(int[] prices) {
        int res = 0; 
        for(int i = 0; i < prices.length; i ++){
            if(prices[i] < minPrice){
                minPrice = prices[i];
            }else if(prices[i] > minPrice){
                res = Math.max(res, prices[i] - minPrice);
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

思路二：动态规划

这题的思路跟打家劫舍的思路也很类型，我们也可以分为，到第i天结束时是否买入了股票（买入和没有买入）

定义二维数组：f[n][2]

状态表示：

f[i][0] 表示第i天没有持有股票所得最大现金（利润）

f[i][1] 表示第i天持有股票所得最大现金（利润）

状态计算：

• f[i][0] = max(f[i - 1][0], f[i - 1][1] + prices[i]
• f[i][1] = max(f[i - 1][1], -prices[i])
  • 第i-1天就持有股票，那么就保持现状（不买入），所得现金就是昨天持有股票的所得现金 即：dp[i - 1][1]
  • 第i天买入股票（买入），所得现金就是买入今天的股票后所得现金即：-prices[i]

初始化：

• f[0][1] = -prices[0];
• f[0][0] = 0;

结果返回：f[n - 1][0]：最后一天不持有股票的最大利润（要么买了股票然后卖出去赚钱了，要么没买即为0）

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

        f[0][1] = -prices[0];
        f[0][0] = 0;
        for(int i = 1; i < n; i ++){
            f[i][0] = Math.max(f[i - 1][0], f[i - 1][1] + prices[i]);
            f[i][1] = Math.max(f[i - 1][1], -prices[i]);
        }
        return f[n - 1][0];
    }   
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

24. 买卖股票的最佳时机II

题目链接：122. 买卖股票的最佳时机 II - 力扣（LeetCode）

本题和题I的唯一区别本题股票可以买卖多次了（注意只有一只股票，所以再次购买前要出售掉之前的股票）!

Code

思路一：贪心：只要能赚我们就进行买卖操作（前一天比后一天小，后一天我们就卖出，能赚即赚）

class Solution {
    public int maxProfit(int[] prices) {
        int res = 0;
        for(int i = 1; i < prices.length; i ++){
            if(prices[i] > prices[i - 1]){
                res += (prices[i] - prices[i - 1]);
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11

思路二：动态规划

跟上个题一样的思考方式，f[n][2]

状态表示：

f[i][0] 表示第i天没有持有股票所得最大现金（利润）

f[i][1] 表示第i天持有股票所得最大现金（利润）

状态计算（可以买多次，再次购买前要出售掉之前的股票）：

• f[i][0] = max(f[i - 1][0], f[i - 1][1] + prices[i])
• f[i][1] = max(f[i - 1][1], f[i - 1][0] - prices[i])

初始化：

• f[0][0] = 0
• f[0][1] = -prices[i]

结果返回：f[n - 1][0]：最后一天不持有股票的最大利润（要么买了许多股票然后卖出去赚钱了，要么没买即为0）

对比 买卖股票的最佳时机I，我们发现只有f[i][1]不同，原因就是II可以买卖多次就要积累前面赚到的最大利润，而I只能买卖一次，刚刚买入时利润必定是-prices[i]

• f[i][0] = max(f[i - 1][0], f[i - 1][1] + prices[i]
• f[i][1] = max(f[i - 1][1], -prices[i])

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

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

题目链接：123. 买卖股票的最佳时机 III - 力扣（LeetCode）

本题最多可以完成 两笔 交易。

动态规划老三样：状态定义、状态转移、初始状态。

不难想出本题的状态转移方程需要三个维度：f[i][0..2][0..2]

• 维度一：第几天
• 维度二：完成交易的笔数
• 维度三：是否持有股票

状态表示：

• f[i][k][0]：表示第i天没有持有股票且完成的交易次数为k所得最大现金（利润）
• f[i][k][1]：表示第i天持有股票且完成的交易次数为k所得最大现金（利润）

状态计算（转移）：

• f[i][k][0] = max(f[i - 1][k][0], f[i - 1][k - 1][1] + prices[i])
• f[i][k][1] = max(f[i - 1][k][1], f[i - 1][k][0] - prices[i])

其中k的范围：1 <= k <= 2

特别的，当k为0时：

• f[i][0][0] = 0
• f[i][0][1] = max(f[i - 1][0][1], f[i - 1][0][0] - prices[i])，（前面的天数可能买入了但没有卖出（没有完成交易））

状态初始化：

初始状态就是上面提到的第一种情况，没有进行过任何交易 dp[i][0][0] = 0；此外还有可能在第一天就重复买卖了一次或者两次，dp[0][0..2][0] = 0，dp[0][0..2][1] = -prices[i]

Code

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][][] f = new int[n + 10][3][2];

        // 初始化
        for(int k = 0; k <= 2; k ++){
            f[0][k][0] = 0;
            f[0][k][1] = -prices[0];
        }
        for(int i = 1; i < n; i ++){
            for(int k = 0; k <= 2; k ++){// 最多完成两笔交易
                if(k == 0){// 特判
                    f[i][k][0] = 0;
                    f[i][k][1] = Math.max(f[i - 1][k][1], f[i - 1][k][0] - prices[i]);
                }else { // k：[1,2] 
                    f[i][k][0] = Math.max(f[i - 1][k][0], f[i - 1][k - 1][1] + prices[i]);
                    f[i][k][1] = Math.max(f[i - 1][k][1], f[i - 1][k][0] - prices[i]);
                }
            }
        }
        return f[n - 1][2][0];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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

题目链接：188. 买卖股票的最佳时机 IV - 力扣（LeetCode）

上一题是最多完成两笔而本题最多可以完成 K 笔交易

直接套用上一题的代码即可，把最多完成2笔换成最多完成**K**即可

Code

class Solution {
    public int maxProfit(int K, int[] prices) {
        int n = prices.length;
        int[][][] f = new int[n + 10][K + 1][2];

        // 初始化
        for(int k = 0; k <= K; k ++){
            f[0][k][0] = 0;
            f[0][k][1] = -prices[0];
        }
        for(int i = 1; i < n; i ++){
            for(int k = 0; k <= K; k ++){// 最多完成K笔交易
                if(k == 0){// 特判
                    f[i][k][0] = 0;
                    f[i][k][1] = Math.max(f[i - 1][k][1], f[i - 1][k][0] - prices[i]);
                }else { // k：[1,2] 
                    f[i][k][0] = Math.max(f[i - 1][k][0], f[i - 1][k - 1][1] + prices[i]);
                    f[i][k][1] = Math.max(f[i - 1][k][1], f[i - 1][k][0] - prices[i]);
                }
            }
        }
        return f[n - 1][K][0];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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

题目链接：309. 最佳买卖股票时机含冷冻期 - 力扣（LeetCode）

本题的关键在于存在冷冻期，不能随便买，如果当天卖出后，下一天不能购入股票，必须等一天（冷冻期），为此我们推导状态转移方程时要再多往前一天推导！

状态表示：

f[i][0] 表示第i天没有持有股票所得最大现金（利润）

f[i][1] 表示第i天持有股票所得最大现金（利润）

状态计算（状态转移推导过程如下）：

状态计算：

• f[i][0] = max(f[i - 1][0], f[i - 1][1] + prices[i])
• f[i][1] = max(f[i - 1][1], f[i - 2][0] - prices[i])

初始化：

• f[0][0] = 0
• f[0][1] = -prices[0]

由于状态转移方程用到i - 2的状态，由于我们从下标1开始枚举，那么就会存在f[-1][0]的情况，倒数1天为买入，那也是0，为此特判一下即可（数组下标不能为负数）

Code

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

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

题目链接：714. 买卖股票的最佳时机含手续费 - 力扣（LeetCode）

本题不存在存在冷冻期，只是多了卖出时要支付的手续费而已（相比于买卖股票2），还是常规思路：

状态表示：

f[i][0] 表示第i天没有持有股票所得最大现金（利润）

f[i][1] 表示第i天持有股票所得最大现金（利润）

状态计算：

• f[i][0] = max(f[i - 1][0], f[i - 1][1] + prices[i] - fee)，后面的状态表示卖出，那么就要从利益中扣去手续费
• f[i][1] = max(f[i - 1][1], f[i - 1][0] - prices[i])

Code

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