Vesper_Lynd's blog

dp problem what makes the difference between the two?
By Vesper_Lynd, history, 6 years ago, In English

Submission 1 in this code my solution accepts if i inititiate dp with -1; Submission 2 in this code my solution exceeds if i inititiate with dp=0 what makes the difference between the 2? i know if d>n dp=0 but i have covered that solution already so what further cases it counts uselessly,please help!! Problem Source

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

Stab in the dark, but what if value for some cell is actually a multiple of M? It will be stored as 0 and every time you will need it you will have to recalculate, because you have no way to say whether it was already calculated or not. But if you set "non-value" as -1 then the problem disappears since calculated value cannot be equal to -1, since it is always in the range [0, M-1].

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

If some dp[i][j] is divisible by mod (1e9+7) then it will be calculated multiple times.

→ Reply