题解 | #牛群买卖计划II#

• 题目考察的知识点 : 动态规划
• 题目解答方法的文字分析：

1. 可以使用一个三维数组 f 来表示在第 i 天进行了 j 次买卖时能够获得的最大利润，其中 f[i][j][0] 表示在第 i 天结束时手中没有牛的最大利润，f[i][j][1] 表示在第 i 天结束时手中持有一只牛的最大利润
2. 对于 f[i][j][0]，它可以由以下两种状态转移而来：第 i 天结束时手中没有牛，可能是前一天也没有牛，即 f[i-1][j][0]，或者是前一天结束时手中持有一只牛，然后在第 i 天将其卖掉，即 f[i-1][j][1] + prices[i]；对于不进行任何操作的情况，即 f[i-1][j][0]
3. 对于 f[i][j][1]，它可以由以下两种状态转移而来：第 i 天结束时手中持有一只牛，可能是前一天就已经持有了，即 f[i-1][j][1]，或者是前一天结束时手中没有牛，然后在第 i 天购买了一只牛并持有，即 f[i-1][j-1][0] - prices[i]；对于不进行任何操作的情况，即 f[i-1][j][1]。
4. 最终的答案即为 f[n-1][k][0]

• 本题解析所用的编程语言: Python
• 完整且正确的编程代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param prices int整型一维数组
# @param k int整型
# @return int整型
#
class Solution:
    def maxProfitII(self, prices: List[int], k: int) -> int:
        n = len(prices)
        if n == 0 or k == 0:
            return 0
        if k >= n // 2:
            # 如果 k 大于等于交易次数的上限，相当于可以进行无限次交易，
            # 这种情况下可以使用贪心算法进行求解。
            return self.maxProfitGreedy(prices)
        # 初始化 f 数组
        f = [[[0 for _ in range(2)] for _ in range(k + 1)] for _ in range(n)]
        for i in range(k + 1):
            f[0][i][0] = 0
            f[0][i][1] = -prices[0]
        for i in range(1, n):
            for j in range(k + 1):
                f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1] + prices[i])
                if j > 0:
                    f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - prices[i])
                else:
                    f[i][j][1] = float("-inf")
        # 找出最大值
        res = 0
        for i in range(k + 1):
            res = max(res, f[n - 1][i][0])
        return res

    def maxProfitGreedy(self, prices: List[int]) -> int:
        res = 0
        for i in range(1, len(prices)):
            if prices[i] > prices[i - 1]:
                res += prices[i] - prices[i - 1]
        return res