跳转至

3573. 买卖股票的最佳时机 V

题目描述

给你一个整数数组 prices，其中 prices[i] 是第 i 天股票的价格（美元），以及一个整数 k。

你最多可以进行 k 笔交易，每笔交易可以是以下任一类型：

  • 普通交易：在第 i 天买入，然后在之后的第 j 天卖出，其中 i < j。你的利润是 prices[j] - prices[i]。

  • 做空交易：在第 i 天卖出，然后在之后的第 j 天买回，其中 i < j。你的利润是 prices[i] - prices[j]。

注意：你必须在开始下一笔交易之前完成当前交易。此外，你不能在已经进行买入或卖出操作的同一天再次进行买入或卖出操作。

通过进行 最多 k 笔交易，返回你可以获得的最大总利润。

 

示例 1:

输入: prices = [1,7,9,8,2], k = 2

输出: 14

解释:

我们可以通过 2 笔交易获得 14 美元的利润：
  • 一笔普通交易：第 0 天以 1 美元买入，第 2 天以 9 美元卖出。
  • 一笔做空交易：第 3 天以 8 美元卖出，第 4 天以 2 美元买回。

示例 2:

输入: prices = [12,16,19,19,8,1,19,13,9], k = 3

输出: 36

解释:

我们可以通过 3 笔交易获得 36 美元的利润：
  • 一笔普通交易：第 0 天以 12 美元买入，第 2 天以 19 美元卖出。
  • 一笔做空交易：第 3 天以 19 美元卖出，第 4 天以 8 美元买回。
  • 一笔普通交易：第 5 天以 1 美元买入，第 6 天以 19 美元卖出。

 

提示:

  • 2 <= prices.length <= 103
  • 1 <= prices[i] <= 109
  • 1 <= k <= prices.length / 2

解法

方法一：动态规划

我们定义 \(f[i][j][k]\) 表示在前 \(i\) 天内，最多进行 \(j\) 笔交易，且当前状态为 \(k\) 时的最大利润。这里的状态 \(k\) 有三种可能：

  • 若 \(k = 0\)，表示当前没有持有股票。
  • 若 \(k = 1\)，表示当前持有一支股票。
  • 若 \(k = 2\)，表示当前持有一支股票的空头。

初始时，对任意 \(j \in [1, k]\)，都有 \(f[0][j][1] = -prices[0]\) 和 \(f[0][j][2] = prices[0]\)。这表示在第 0 天买入一支股票或卖出一支股票的空头。

接下来，我们可以通过状态转移来更新 \(f[i][j][k]\) 的值。对于每一天 \(i\) 和每笔交易 \(j\)，我们可以根据当前状态 \(k\) 来决定如何更新：

  • 若 \(k = 0\)，表示当前没有持有股票，这个状态可以由以下三种情况转移而来：
    • 前一天没有持有股票。
    • 前一天持有一支股票，并在今天卖出。
    • 前一天持有一支股票的空头，并在今天买回。
  • 若 \(k = 1\)，表示当前持有一支股票，这个状态可以由以下两种情况转移而来：
    • 前一天持有一支股票。
    • 前一天没有持有股票，并在今天买入。
  • 若 \(k = 2\)，表示当前持有一支股票的空头，这个状态可以由以下两种情况转移而来：
    • 前一天持有一支股票的空头。
    • 前一天没有持有股票，并在今天卖出。

即，对于 \(1 \leq i < n\) 和 \(1 \leq j \leq k\)，我们有以下状态转移方程：

\[ \begin{aligned} f[i][j][0] &= \max(f[i - 1][j][0], f[i - 1][j][1] + prices[i], f[i - 1][j][2] - prices[i]) \\ f[i][j][1] &= \max(f[i - 1][j][1], f[i - 1][j - 1][0] - prices[i]) \\ f[i][j][2] &= \max(f[i - 1][j][2], f[i - 1][j - 1][0] + prices[i]) \end{aligned} \]

最终，我们需要返回 \(f[n - 1][k][0]\)，即在前 \(n\) 天内，最多进行 \(k\) 笔交易，且当前没有持有股票时的最大利润。

时间复杂度 \(O(n \times k)\)，空间复杂度 \(O(n \times k)\)。其中 \(n\) 为数组 \(\textit{prices}\) 的长度，而 \(k\) 为最大交易次数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def maximumProfit(self, prices: List[int], k: int) -> int:
        n = len(prices)
        f = [[[0] * 3 for _ in range(k + 1)] for _ in range(n)]
        for j in range(1, k + 1):
            f[0][j][1] = -prices[0]
            f[0][j][2] = prices[0]
        for i in range(1, n):
            for j in range(1, k + 1):
                f[i][j][0] = max(
                    f[i - 1][j][0],
                    f[i - 1][j][1] + prices[i],
                    f[i - 1][j][2] - prices[i],
                )
                f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - prices[i])
                f[i][j][2] = max(f[i - 1][j][2], f[i - 1][j - 1][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
class Solution {
    public long maximumProfit(int[] prices, int k) {
        int n = prices.length;
        long[][][] f = new long[n][k + 1][3];
        for (int j = 1; j <= k; ++j) {
            f[0][j][1] = -prices[0];
            f[0][j][2] = prices[0];
        }
        for (int i = 1; i < n; ++i) {
            for (int j = 1; j <= k; ++j) {
                f[i][j][0] = Math.max(f[i - 1][j][0],
                    Math.max(f[i - 1][j][1] + prices[i], f[i - 1][j][2] - prices[i]));
                f[i][j][1] = Math.max(f[i - 1][j][1], f[i - 1][j - 1][0] - prices[i]);
                f[i][j][2] = Math.max(f[i - 1][j][2], f[i - 1][j - 1][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
class Solution {
public:
    long long maximumProfit(vector<int>& prices, int k) {
        int n = prices.size();
        long long f[n][k + 1][3];
        memset(f, 0, sizeof(f));
        for (int j = 1; j <= k; ++j) {
            f[0][j][1] = -prices[0];
            f[0][j][2] = prices[0];
        }

        for (int i = 1; i < n; ++i) {
            for (int j = 1; j <= k; ++j) {
                f[i][j][0] = max({f[i - 1][j][0], f[i - 1][j][1] + prices[i], f[i - 1][j][2] - prices[i]});
                f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - prices[i]);
                f[i][j][2] = max(f[i - 1][j][2], f[i - 1][j - 1][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
func maximumProfit(prices []int, k int) int64 {
    n := len(prices)
    f := make([][][3]int, n)
    for i := range f {
        f[i] = make([][3]int, k+1)
    }

    for j := 1; j <= k; j++ {
        f[0][j][1] = -prices[0]
        f[0][j][2] = prices[0]
    }

    for i := 1; i < n; i++ {
        for j := 1; j <= k; j++ {
            f[i][j][0] = max(f[i-1][j][0], f[i-1][j][1]+prices[i], f[i-1][j][2]-prices[i])
            f[i][j][1] = max(f[i-1][j][1], f[i-1][j-1][0]-prices[i])
            f[i][j][2] = max(f[i-1][j][2], f[i-1][j-1][0]+prices[i])
        }
    }

    return int64(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
25
function maximumProfit(prices: number[], k: number): number {
    const n = prices.length;
    const f: number[][][] = Array.from({ length: n }, () =>
        Array.from({ length: k + 1 }, () => Array(3).fill(0)),
    );

    for (let j = 1; j <= k; ++j) {
        f[0][j][1] = -prices[0];
        f[0][j][2] = prices[0];
    }

    for (let i = 1; i < n; ++i) {
        for (let j = 1; j <= k; ++j) {
            f[i][j][0] = Math.max(
                f[i - 1][j][0],
                f[i - 1][j][1] + prices[i],
                f[i - 1][j][2] - prices[i],
            );
            f[i][j][1] = Math.max(f[i - 1][j][1], f[i - 1][j - 1][0] - prices[i]);
            f[i][j][2] = Math.max(f[i - 1][j][2], f[i - 1][j - 1][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
impl Solution {
    pub fn maximum_profit(prices: Vec<i32>, k: i32) -> i64 {
        let n = prices.len();
        let k = k as usize;
        let mut f = vec![vec![vec![0i64; 3]; k + 1]; n];
        for j in 1..=k {
            f[0][j][1] = -(prices[0] as i64);
            f[0][j][2] = prices[0] as i64;
        }
        for i in 1..n {
            for j in 1..=k {
                f[i][j][0] = f[i - 1][j][0]
                    .max(f[i - 1][j][1] + prices[i] as i64)
                    .max(f[i - 1][j][2] - prices[i] as i64);
                f[i][j][1] = f[i - 1][j][1].max(f[i - 1][j - 1][0] - prices[i] as i64);
                f[i][j][2] = f[i - 1][j][2].max(f[i - 1][j - 1][0] + prices[i] as i64);
            }
        }
        f[n - 1][k][0]
    }
}

评论