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.

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.

When writing a loop where a lot of things happen, it is good to describe to yourself what your 'loop invariant' is.

To describe this, let me first give you an example problem. say you have a snowy mountain, and to go up it, you can either walk between ski stations, or take a ski lift. There are N number of stations, and from any station there is exactly one ski lift to another higher (not necessarily unique) station. The place where each ski lift takes you is given in input of N lines consisting of where the i-th value tells you where the ski lift from the i-th station takes you. How many possible ways are there to reach the top, provided you only move upwards.

This problem is clearly dp, and usually, I’d go about this with a bottom-up for loop.

bottom-up: I start by solving it for the first few terms, and then build up my answer.

so at the moment, my information tells me where the i’th ski lift takes me to, but we’re trying to find the way to get TO a particular place, so lets change this: (I hope you know c++)

int endArray[N]; //input for N stations vector startArray[N]; //what I want; for each station, where can I come from to get to it

for (int i = 0; i < N; i++){ startArray[endArray[i]].push_back(i); /* since each station only has one lift going away, I only need to do it once per station. I am taking the i-th station and writing its position to its destination so I know where to look back to for paths. */ }

Sorry for the what has so far been the equivalent of boilerplate, let me get to the point:

The loop invariant is a statement that is true at the start of each iteration and while its validity may change during the contents of the loop, if you’ve written it right, then it should be true by the end. The key point of the contents though, is to make sure the loop invariant works even while i (or any iterator value) changes. Now you want to decide your loop invariant on the basis of, ‘what do I want at the end’

and I want to know all the possible paths to a particular point, so I shall make that my invariant

now, heres where you can pick your base case: find a point at which you don’t need any information to know that it is true. Here, I’d say the very beginning: no distance, no choice, so only one possibility

you’re already there and there’s no other way you could’ve gotten there

So you should start with your base case of an array of all 0s but the first term is one

now, you go up the hill. Lets assume that one test case is that each ski lift skips one station, so the i-th number will be i+2. So at the second station, there is no incoming lift, only a path from walking, so only 1 way to get to it. The third station has a lift from the first, or you could walk from the second. at each of these previous points, there was only one way to get to them, so there are a total of two ways to get to the third. you can take a lift from the second station, or walk from the third to get to the fourth, so there is a total of 1+2 ways to get there.

For each station I go through, I find the number of ways to get to it, making sure I get all the information I could need from it then, so that later, I can pull that information to use reliably. Using a loop invariant becomes quite similar to induction in maths, so provided your logic is correct, the answer is guaranteed.

If you are having trouble with mistakes in DP problems, try deciding on a loop invariant, and then work from there, because then you can be guaranteed that you've picked a good base case, and that your final answer should be correct

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.

1. 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.

2. 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.

3. 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.