买卖股票的最佳时机 IV

Question

Link: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/

public int maxProfit(int k, int[] prices) {        
    int[] buy = new int[k + 1], sell = new int[k + 1];
    Arrays.fill(buy, Integer.MIN_VALUE);
    for (int price : prices) {
        for (int i = 1; i <= k; i++) {
            buy[i] = Math.max(buy[i], sell[i - 1] - price);
            sell[i] = Math.max(sell[i], buy[i] + price);
        }
    }
    return sell[k];
}

问题 1) 我理解大部分解决方案，但我对 sell[i] 状态有点困惑。比如我们在buy[i]买入一只股票，计算方式是sell[i - 1] - price，即前一天卖出的最大利润减去今天买入股票的成本。

然而，当我们在sell[i]中买入一只股票时，它是buy[i] + price而不是buy[i-1]。如果我们今天要卖出，不应该是昨天买入的最大利润+今天的价格吗？所以想知道为什么在计算sell[i]时缺少+1。

问题2) 除了买入或卖出，我们还可以选择持有而不做任何事情，表示为 buy[i]/sell[i]。但是，如果我们今天什么都不做，这个数字不应该是前一天的重复数字吗？ buy[i+1]/sell[i+1]。只是想知道为什么它是 buy[i] 而不是 buy[i-1] 因为在其他股票问题中，当你选择什么都不做时，你会获取前一天的价值。

Answer 1

请注意，索引 i 从 1 到允许的交易数 k。这意味着在这个解决方案中 i - 1 不是前一天，而是前一天的交易。

在每次外部循环迭代开始时，buy 和 sell 数组已经存储了前一天的值。因此，在更新 buy[i] 和 sell[i] 之前的内部循环中，该索引处的值来自前一天。

所以内部循环中的行的意思其实是这样的：

buy[i] =                  // the best funds after buying in the i-th transaction is
  Math.max(               // the max of
    buy[i],               // not buying today at all, 
                          // i.e. just copy the value from yesterday
    sell[i - 1] - price); // or buying for today's price with the funds 
                          // after selling in the **previous** transaction
sell[i] =                 // the best funds after selling in the i-th transaction is
  Math.max(               // the max of
    sell[i],              // not selling today at all, 
                          // i.e. just copy the value from yesterday
    buy[i] + price);      // or selling for today's price with the funds
                          // after buying in the **current** transaction

请注意，当天一笔买卖其实是没有问题的。价格相同，所以这意味着我们只忽略第 i 笔交易。这意味着最终 sell[k] 将包含 k 或更少笔交易后的最佳利润。没关系：例如，在第一个示例测试用例中 k = 2, prices = [2,4,1] 我们仅使用 2 个允许的事务之一。

买卖股票的最佳时机 IV

Best Time to Buy and Sell Stock IV

algorithm

dynamic-programming