Блог пользователя tony_sterk

How to optimize this recurrence?
Автор tony_sterk, история, 5 лет назад, По-английски

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}
  • Проголосовать: нравится
  • -22
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

is this from that ongoing scaler-academy iiit contest?

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

→ Ответить