tony_sterk's blog

How to optimize this recurrence?
By tony_sterk, history, 6 years ago, In English

Is there any optimisation for this given recurrence

DP[i][j] = min(DP[k][j - 1] + sum of arr(i to k - 1), DP[i][j]);
{0 <= i < n}
{i < k < n}
{0 <= j <= B}
  • Vote: I like it
  • -22
  • Vote: I do not like it

Comments Comments (9)
| Write comment?
»
6 years ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

is this from that ongoing scaler-academy iiit contest?

→ Reply
»
6 years ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

You can do prefix sums on DP and also on arr to reduce to N^2

→ Reply
»
6 years ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

Auto comment: topic has been updated by tony_sterk (previous revision, new revision, compare).

→ Reply