### rachitiitr's blog

By rachitiitr, history, 8 years ago,

The question I am asking is very vague but if some experts can share some of their tricks or tips while solving DP questions would be really helpful. The problems I face is how to think of such complex DP states, and even if I think of them, how should I initialse the base values(e.g dp[0][0] = 1or0). Consider the two problems
1. D. Magic Numbers
2. B. Numbers
Both of them have DP based solutions.
Brief Solution: dp[i][j][k] is our dp state that represents number of magic prefixes of length i with remainder j modulo m. If k  =  0 than the prefix should be less than the corresponding prefix in n and if k  =  1 then the prefix should be equal to the prefix of n (it can not be greater).
First of all, how does one realises the need of having that [k] in out DP. Also in the solution, for k = 0, line 54 is letting the digit at new position be greater than a[i]. I understand that the over all number should be less than or equal to the prefix of our original number. So the digits in the number we are forming can exceed the digit at corresponding position in original number a, but how is everything working is really difficult to think. How are so many people able to think about it and how do they begin to solve such DP problems?

Let's assume I magically understood the DP state. After that, the problem I faced was to initialise the base values. I was going to initialise the dp[1][j][k] values but that would be too longer. On looking at the solution, dp[0][0][1] = 1 was enough. It took me time to see how magically it was finding the correct answers.