给定: DP[i][j]=DP[i-1][j] + DP[i-1][j-1]*C[i]
我想计算 DP[n][m]。我知道可以计算所有的 DP[][] 值,但我想要一个适用于较大的 N 和 M(高达45000)的解决方案。有没有更快的方法?
给定: 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]