[Help] Finding the DP state in problem and Initialising the base cases

Revision en1, by rachitiitr, 2016-05-26 17:40:58

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.

Brief Solution: dp[i][j] is our dp state that represents numbers of length i formed by using digits from [j, 9]. Thus dp[i][j] +  = dp[i - x][j + 1] * C[i][x], where x is number of times I use digit j. Perfect! But what I could think of is that I have to count the number of permutations of length [sum(a[i]), n] such that occ[i] >  = a[i], and I began to think of how to solve this.

I clearly understand that more practise is needed, but seeing the tutorials for DP problems I was wondering whether there are some DP states that are very common or some standard DP techniques that one must master. One example being the usage of "Subset Hack" in E. Compatible Numbers. I couldn't even find tutorial on what "Subset Hack" is.

History

Revisions

Rev. Lang. By When Δ Comment
en1 rachitiitr 2016-05-26 17:40:58 2767 Initial revision (published)