I've been able to form a recurrence relation with memoization in a recursive approach for most problems but the online coding rounds exceed the time limit or stack overflow occurs in all these problems. An iterative approach seems to be the only way out. But coming up with logic for filling the DP table is frustrating and difficult. Are there steps with which we can convert any recurrence relation into a DP table calculation?
- Analyse the problem and find out which values you have to compute and how they depend on each other.
- Make a table that can hold these values with somewhat intuitive indices, and fill it in an order that is easy to follow, but doesn't conflict with the dependencies.
I'm afraid it's hard to be any more specific here, as the values, their enumeration and the dependencies between them, all vary widely between problems.