Compute DP[n][m] faster

Question

Given: 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 compute all the DP[][] values, but I want a solution for typically larger N & M( upto 45000 ). Is there any way to do it faster ?

Answer 1

Time complexity-wise I don't think you can get much better without any additional information. However, you can compute the matrix row by row, leading to an improved space efficiency 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 correspond to current_row[m] in the end

Answer 2

I totally second the answer of Niklas B. in the aspect that the implementation cannot be made faster complexity-wise, however you could use memoization instead of 'true' dynamic programming. Although it does not improve the worst-case complexity, it potentially results in calculation of fewer intermediate values.