tony_sterk's blog

How to optimize this recurrence?
By tony_sterk, history, 5 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?
»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

is this from that ongoing scaler-academy iiit contest?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Yeah it was from scaler acadmey contest which i have just completed!!! Screenshot-from-2020-05-11-22-59-31.png

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      I was curious for answers that's why i posted it on codeforces :)

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        the contest is not over yet. dont spoil before the contest ends.

        → Reply
»
5 years ago, # |
  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
»
5 years ago, # |
  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