Need Help in resolving TLE in DP with memo and iterative.

Revision en1, by Codeforcer, 2021-03-09 14:54:46

Why do some solutions containing dp with memoization result in TLE but the same iterative version always passes? I have had this doubt for quite a while.

For example this problem : https://codeforces.net/contest/628/problem/D

DP+Memo->TLE

Checking the editorial they have done the same thing just iterative.

So my questions are this :

->What should be a good practice to write dp memoized or iterative?

->Can every memoized dp problem be converted to iterative ?

->What exactly goes wrong with memoized versions getting TLE'd ?

->How to resolve such TLE's ?

Thanks!

Tags dp, #memoization, iterative, digit dp

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Codeforcer 2021-03-09 14:54:46 2286 Initial revision (published)