理解买卖股票最佳时机的简明DP解法IV

Question

问题是著名的leetcode problem（或类似其他语境），最好买卖股票，最多k笔交易。这是问题的屏幕截图：

我正在尝试理解这个 DP 解决方案。您可以忽略大 k 的第一部分。我不明白 dp 部分为什么有效。

class Solution(object):
    def maxProfit(self, k, prices):
        """
        :type k: int
        :type prices: List[int]
        :rtype: int
        """
        # for large k greedy approach (ignore this part for large k)
        if k >= len(prices) / 2:
            profit = 0
            for i in range(1, len(prices)):
                profit += max(0, prices[i] - prices[i-1])
            return profit

#       Don't understand this part 
        dp = [[0]*2 for i in range(k+1)]
                             
        for i in reversed(range(len(prices))):
            for j in range (1, k+1):
                dp[j][True] = max(dp[j][True], -prices[i]+dp[j][False])
                dp[j][False] = max(dp[j][False], prices[i]+dp[j-1][True])
            
        return dp[k][True]

我能够驱动类似的解决方案，但它使用两行（dp 和 dp2）而不是仅一行（上面解决方案中的 dp）。对我来说，解决方案似乎正在覆盖自身的值，对于该解决方案而言，这看起来不正确。然而，答案有效并通过了 leetcode。

Answer 1

让我们说一下：

for i in reversed(range(len(prices))):

在考虑以后的价格后，我们预先知道的每个未来价格。

  for j in range (1, k+1):

对于将此价格视为k双价交易之一的每种可能性。

    dp[j][True] = max(dp[j][True], -prices[i]+dp[j][False])

如果我们认为这可能是一次购买——因为我们在时间上倒退，一次购买意味着完成交易——我们选择 (1) 中最好的已考虑第 j 次购买（dp[j][True]）或 (2) 减去此价格作为购买并添加我们已经包含第 j 次销售的最佳结果（-prices[i] + dp[j][False]).

    dp[j][False] = max(dp[j][False], prices[i]+dp[j-1][True])

否则，我们可能会将其视为一次销售（交易的前半部分，因为我们要倒退），因此我们选择 (1) 已经考虑过的第 j 次销售中最好的（dp[j][False]), 或 (2) 我们将此价格添加为销售，并添加我们迄今为止为第一个 (j - 1) 完成交易 (prices[i] + dp[j-1][True]) 获得的最佳结果。

请注意，第一个 dp[j][False] 指的是第 j 个“半交易”，如果您愿意，可以进行销售，因为我们在时间上倒退，那将是在较晚价格的较早迭代。然后，我们可能会考虑将这个价格作为第 j 次销售来覆盖它。

理解买卖股票最佳时机的简明DP解法IV

Understanding the concise DP solution for best time to buy and sell stocks IV

algorithm

dynamic-programming