algorithm - 尝试将 DP 解决方案从 2D Array 优化到 1D Array

通常，当可以从其子问题的最优解中确定给定问题的最优解时，我们使用可以应用 DP。在为某些算法提出解决方案时，首先提出递归解决方案通常会有所帮助。从那里，如果我们观察到递归子问题被重新计算多次，我们可以只记住中间结果以便以后快速参考它们。

在某些特殊情况下，我们实际上并不需要一次记住所有子问题的解决方案；我们只需要一次知道某个子集。

上面描述的空间优化似乎是您所问问题的最佳答案 - 如何将整个解决方案集作为 2D 矩阵压缩为单个 1D 数组？好吧，在给定时间，我们实际上并没有将所有解决方案（2D 矩阵）存储在任何单个时间点。我们只存储在算法中计算下一轮中间/最终输出所需的内容。

也许浏览一个示例应用程序可能有助于加强这种描述。一个很好的例子是广义的股票交易问题。基本上，我们prices在给定日期有一个股票的输入数组，并且想要计算如果k进行买卖交易可以赚取的最大利润，其中可以在任何给定时间购买和持有一只股票。

在我看来，最棘手的部分是弄清楚如何从一个交易案例转移到两个交易案例。我假设我们在动态编程方面足够精通，可以立即转向k事务案例。请注意，就子问题而言，问题的一个很好的表述如下：

prices = input array of prices, length is n
Define dp[k][i] = maximum profit earned by day i, after having made k transactions
dp[k][i] = max(dp[k][i - 1], (prices[i] + effectivePrice)
effectivePrice = max(dp[k - 1][i] - prices[i], effectivePrice) (compute on the fly for each i)

现在在这种特殊情况下，我们的“天真” dp 解决方案有一个包含k行和n列的二维矩阵。这里的空间缩减是，为了计算k交易的结果，我们只需要k - 1交易案例的知识。因此，当然可以使用两个大小为的一维数组来解决问题n。

Let oldDp = solution for the k - 1 case
Let newDp = solution for the k case (computed on the fly)
for each transaction:
    for each day i:
        newDp[i] = max(newDp[i - 1], (prices[i] + effectivePrice)
        effectivePrice = max(oldDp[i] - prices[i], effectivePrice)

    // Set up for next iteration
    oldDp = newDp
    newDp = blank array of size n

正如我们所看到的，我们设法节省了大量空间——我们从不得不使用具有k行和n列的 2D 矩阵变成了两个大小为的 1D 数组n。更好的优化是只使用一个一维数组；这是可能的，因为我们检查的唯一索引是计算时oldDp的当前索引。因为我们只需要临时记住 day 的旧结果，所以我们可以使用一个临时变量。因此，优化的伪代码（对于我们的“幼稚”方法）如下所示：ieffectivePricei

Let dp = maximum profit, so that dp[i] = maximum profit after k transactions (built iteratively) on day i.
for each transaction:
    for each day i:
        // At this point, dp[i] is equivalent to dp[k - 1][i], yet
        // for all j < i, dp[j] is equivalent to dp[k][j]!
        temp = dp[i]
        dp[i] = max(dp[i - 1], prices[i] + effectivePrice)
        effectivePrice = max(temp - prices[i], effectivePrice)

因此，使用k从k - 1交易中确定最佳解决方案的“幼稚”想法，我们通过从大小为 2D 的矩阵到大小kn为的一维数组来优化空间n。

algorithm - 尝试将 DP 解决方案从 2D Array 优化到 1D Array

问题描述

解决方案

推荐阅读