买卖股票的最佳时机 IV

难度:

标签:

题目描述

给你一个整数数组 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 <= k <= 100
1 <= prices.length <= 1000
0 <= prices[i] <= 1000

代码结果

运行时间: 160 ms, 内存: 24.5 MB

// Java Stream solution
// 思路：使用Java Stream API来实现相同的逻辑。由于Stream不适合复杂的逻辑，所以我们这里依旧是使用普通的迭代来处理状态转移。
// 代码结构与普通Java方法类似，但在适当的位置使用Stream来简化某些操作。
 
import java.util.stream.IntStream;
 
public class Solution {
    public int maxProfit(int k, int[] prices) {
        if (prices.length == 0) return 0;
        int n = prices.length;
        if (k >= n / 2) return maxProfitUnlimited(prices);
        int[][] dp = new int[k + 1][n];
        for (int j = 1; j <= k; j++) {
            int maxDiff = -prices[0];
            for (int i = 1; i < n; i++) {
                dp[j][i] = Math.max(dp[j][i - 1], prices[i] + maxDiff);
                maxDiff = Math.max(maxDiff, dp[j - 1][i] - prices[i]);
            }
        }
        return dp[k][n - 1];
    }
 
    private int maxProfitUnlimited(int[] prices) {
        return IntStream.range(1, prices.length)
                .filter(i -> prices[i] > prices[i - 1])
                .map(i -> prices[i] - prices[i - 1])
                .sum();
    }
}

解释

方法:

这个题解使用动态规划来解决问题。定义状态 dp[i][k][0] 表示第i天结束后最多进行k次交易且当前没有持有股票的最大利润，dp[i][k][1] 表示第i天结束后最多进行k次交易且当前持有股票的最大利润。然后基于当前是否持有股票、是否发生交易来进行状态转移。最后返回 dp[-1][-1][0] 即最后一天结束后最多进行 k 次交易且没有持有股票的最大利润。

时间复杂度:

O(n*k)

空间复杂度:

O(n*k)

代码细节讲解

🦆

为什么在动态规划的数组定义中需要三个维度，它们分别代表什么意义？

▷

在动态规划的数组定义中，需要三个维度来完整描述问题的状态。第一个维度i代表了天数，用于记录在第i天结束时的状态；第二个维度k代表了允许的最大交易次数，用于跟踪进行到当前的交易次数；第三个维度是二进制，用于表示当前是否持有股票（0表示未持有，1表示持有）。这样的三维表示可以帮助我们存储和更新每一天结束时，在不同交易次数和持有状态下的最大利润。

🦆

在初始化状态时，为什么将 dp[i-1][k][1] 设为负无穷大？这样做有什么特别的意义吗？

▷

在初始化状态时，将 dp[i-1][k][1] 设为负无穷大是为了表示在还没有开始交易之前的不可能状态。因为在第一天之前不可能持有股票，所以设置为负无穷大可以防止这种状态被错误地计算入最优解。此外，这种设置也有利于在动态规划过程中正确处理买入股票的逻辑，确保只有在合适的条件下（即存在足够的交易次数和资金）才会考虑买入操作。

🦆

在进行状态转移时，dp[i][k][0] 和 dp[i][k][1] 的更新公式具体是怎样实现最大利润计算的？

▷

在状态转移时，dp[i][k][0] 的更新公式为 `max(dp[i-1][k][0], dp[i-1][k][1] + prices[i-1])`，这表示当前不持有股票的最大利润可以从两个状态转移而来：维持前一天不持有股票的状态，或者是前一天持有股票并在今天卖出。dp[i][k][1] 的更新公式为 `max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i-1])`，这表示当前持有股票的最大利润可以从两个状态转移而来：维持前一天持有股票的状态，或者是前一天不持有股票并在今天买入（这会消耗一次交易机会）。这两个公式共同确保了在每一天结束时，无论持有状态如何，都能计算出最大的可能利润。

🦆

题解中提到，如果第一天就进行买入操作，这种情况如何在动态规划表中反映？

▷

如果第一天就进行买入操作，这在动态规划表中通过特定的初始化来反映。具体来说，第一天买入股票的情况会在初始化时设置 `dp[1][1][1] = -prices[0]`，表示在第一天结束时，进行了一次交易，并且持有股票，花费了等于第一天股票价格的金额。这种初始化确保了算法能够考虑从第一天开始就进行交易的可能性。

相关问题