algorithm - 更快地计算 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)的解决方案。有什么方法可以更快吗？

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]