### habib_rahman's blog

By habib_rahman, history, 5 years ago,

Actually, I can find the dp states for a problem on average. But for every problem i can't maintain the base case. So, I want tricks from you.

• +11

 » 5 years ago, # | ← Rev. 2 →   +17 You guys are awesome. I want to learn from you. I give a post for help and you all are helping me by -ve votes.
•  » » 5 years ago, # ^ |   +6 It's hard to help if we don't know what you are having problems with. Could you give an example of a problem where you "can't maintain the base case" and explain what you have done?
•  » » » 5 years ago, # ^ |   +1 Thanks for your comment. Like last Hackercup round 1, in problem "Pie" I was trying to solve by recursive dp. But my basecase was wrong. So, Got WA.
•  » » » » 5 years ago, # ^ |   0 Write some code, give a link to the code, post the test case where you have failed.
•  » » 5 years ago, # ^ |   +23 I don't know what is wrong with asking a question. On most of the blog posts when a question is asked, it's always downvoted. I don't understand this. If you know the solution, help the person. If you don't, then there's something for you to learn too. But there's never a reason to downvote someone asking for help.
 » 5 years ago, # |   +20 Try to think of the recurrence relation first without dreading about base cases. Base case really depends on the recurrence itself, doesn't it? And most importantly, solve a LOT of DP problems.
•  » » 5 years ago, # ^ |   0 Thanks a lot Brother.
 » 5 years ago, # |   +17 Let's assume for now that you express the dynamic programming solution with the transition formula, like f (n, k) = f (n, k - 1) + f (n - 1, k) or such. Obviously, this cannot recurse infinitely, so you have to declare something to be a base case. Think of an instance of the problem (perhaps the smallest n or k possible) where the answer is immediately obvious to you. Repeat until every branch of recursion eventually hits one of your base cases.A word of caution here: if you don't have a strong mathematical background, double-check your assumptions about degenerate objects — or just pick the smallest non-degenerate case as the base. It is common to get wrong there, unless you precisely understand how much empty sets are there, what is vacuous truth, or what's the most useful definition of 0 to the power of 0 and why. The good strategy with base cases is to minimize the amount of base cases. The less cases there are, the less place for bugs you will have. See, if you have one formula for the general case and one base case, there are 1+1=2 places to make an error, and each single error will inevitably intrude every path of recursion and be immediately visible when testing. If, on the other side, the number of base cases grows to four, not only there are now 1+4=5 places for a bug, but a bug in one of the base cases won't be visible until the recursion actually hits that case at least once. This, however, contradicts the warning about degenerate objects, so find your own balance between these. Solving a problem by dynamic programming is very similar to mathematical induction: there is a base case, an assumption that everything is already known for lesser parameters, and the transition which is expressed by a formula. So, you can think of the base cases in dynamic programming the same way as you think of the base cases in mathematical induction. After all, you have to use this induction to prove your dynamic programming solution works. If you do it implicitly but have trouble with the base cases, try writing the proof explicitly, and it will have to include the same base cases you need. If the transition formula has too much exceptions — which therefore have to become base cases — this is usually a bad sign for the correctness of the formula itself. The right solution often happens to also be one of the shortest ones, and the ones having very few exceptions, if any. If you produce a formula, start looking for the base cases, and then realize that the formula is incorrect more than once for very small parameters, ask yourself again: why would the formula hold up against large parameters if it doesn't against the ones you can check by hand? Don't proceed until you understand that — or perhaps find out it is plain wrong.