Clever Geek Handbook

Calculate DP [n] [m] faster

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

I want to calculate DP [n] [m]. I know I can calculate all DP [] [] values, but I need a solution for typically large N and M (up to 45000). Is there a way to make it faster?

+3


source to share


2 answers


Time complexity - I don't think you can get much better without any additional information. However, you can compute the matrix row by row, which will result in a space efficiency improvement of O (m) instead of Ξ© (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]

will match current_row[m]

at the end

+1


source


I am entirely Niklas B.'s second answer in the aspect that the implementation cannot be done more complex, but you can use memoization instead of "true" dynamic programming. While this does not improve the worst-case complexity, it potentially results in smaller intermediate values.



0


source






More articles:


All Articles