計算DP [n] [m]更快

Question

鑑於：DP[i][j]=DP[i-1][j] + DP[i-1][j-1]*C[i]

我想計算DP [n] [m]。我知道我可以計算所有DP [] []值，但是我想要一個通常較大的解決方案（最多45000）。 有沒有辦法更快地做到這一點？

Answer 1

時間複雜性我不認爲沒有任何額外的信息你會變得更好。然而，可以計算由行矩陣行，導致O（米）代替Ω（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]到底

Answer 2

我完全第二次回答了Niklas B.在複雜性方面不能做得更快，但是你可以使用memoization而不是'true'動態編程。雖然它不能改善最壞情況的複雜性，但它可能導致計算更少的中間值。