更快地计算 DP[n][m]

Question

给定: DP[i][j]=DP[i-1][j] + DP[i-1][j-1]*C[i]

我想计算 DP[n][m]。我知道可以计算所有的 DP[][] 值，但我想要一个适用于较大的 N 和 M（高达45000）的解决方案。有没有更快的方法？

- steven

---

我认为你最好发布你试图解决的原始问题。 - kraskevich

确实！这是某种背包问题吗？ - Codor

Answer 1

就时间复杂度而言，我认为在没有任何额外信息的情况下你很难得到更好的结果。但是，你可以逐行计算矩阵，从而将空间效率提高到O(m)，而不是Ω(N * M)：

current_row = [X, 0, ...]
prev_row = [0,0,...]
for i := 1 to n:
  copy current_row to prev_row
  # TODO compute current_row[0], recurrence not given
  for j := 1 to i:
    current_row[j] = prev_row[j-1] + C*prev_row[j]

DP[n][m] 最终对应于 current_row[m]

- Niklas B.

Answer 2

我完全同意Niklas B.的回答，他指出实现在复杂度上无法更快，但你可以使用记忆化代替真正的动态规划。虽然这并不改善最坏情况下的复杂度，但可能会减少计算中间值的数量。

- Codor

---

不是真的，因为需要矩阵下对角线的所有值。 - Niklas B.