给定:DP[i][j]=DP[i-1][j] + DP[i-1][j-1]*C[i]
我想计算 DP[n][m]。我知道我可以计算所有 DP[][] 值，但我想要一个通常较大的 N 和 M(高达 45000)的解决方案。 有什么方法可以更快吗？
最佳答案
就时间复杂度而言，我认为如果没有任何其他信息，您不会变得更好。但是，您可以逐行计算矩阵，从而提高 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]
关于algorithm - 更快地计算 DP[n][m]，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30800815/