↓Skip to main content

【LeetCode 188】买卖股票的最佳时机IV

·142 words·1 min
WFUing
Author
WFUing
A graduate who loves coding.
Table of Contents

  • 链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/description/

难点
#

以前做过类似的题目，因为是两个状态之间的变换，很自然地想到有两个dp数组来存储。

  • 用 $in[i][j]$ 表示对于数组 $prices[0…i]$ 中的价格而言，进行恰好 $j$ 笔交易，并且当前手上持有一支股票，这种情况下的最大利润；用 $out[i][j]$ 表示恰好进行 $j$ 笔交易，并且当前手上不持有股票，这种情况下的最大利润。

本题的难点有三个方面：

  1. 关于 $in$ 和 $out$ 数组中 $j$ 的关系，在这里，买入卖出这一整套流程才算一次交易。那么，在卖出的那一刻，1次交易就完成了。那第一次买入，其实是第 0 次交易，第一次卖出，是第 1 次交易结束。
  2. 如何初始化，首先第一天只能买进，不能卖出，而且最多只能有一次交易，那么 $in[0][1…k]$ 和 $out[0][1…k]$ 如何初始化。
  3. 如何更新 $in$ 和 $out$ 数组。

解析
#

代码
# 

class Solution {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        int[][] in = new int[n][k+1];
        int[][] out = new int[n][k+1];
        in[0][0] = -prices[0];
        for(int j = 1; j < k; j++ ) {
            in[0][j] = out[0][j] = -1000;
        }

        for(int i = 1; i < n; i++) {
            in[i][0] = Math.max(in[i-1][0], -prices[i]);
            for(int j = 1; j <=k ; j++) {
                in[i][j] = Math.max(in[i-1][j], out[i-1][j] - prices[i]);
                out[i][j] = Math.max(out[i-1][j], in[i-1][j-1] + prices[i]);
            }
        }

        int maxx = -1;
        for(int j = 0; j <= k; j++) {
            maxx = Math.max(maxx, out[n-1][j]);
        }
        return maxx;
    }
}