# Both bottom-up and top-down dynamic programming style Java code. Good for learners.

• The bottom-up approach is provided as following.
The idea is that we consider from `stair level 0` and `stair level 1`, which are the base cases. And we use an array N to record the number of distinct ways for each level.
Obviously, for `level 0` and `level 1`, the number of distinct ways are 1. After that, for each level `i` where `i` is greater than `0` and `1`, we have 2 possible way to step on it: The first one is to go from `level i - 1` (i.e. climb 1 steps); the second one is to go from `level i - 2` (i.e. climb 2 steps). Thus for each level `i` where `i` is greater than `1`, `N[i] = N[i - 1] + N[i - 2]`.
And hence, `N[n]` stores the total number of distinct ways to climb `n` stairs after the `for` loop.

``````/*
bottom-up approach
*/

public int climbStairs(int n){
if (n == 0){
return 1;
}
else{
int[] N = new int[n + 1];
N[0] = 1;
N[1] = 1;
for (int i = 2; i <= n; i ++){
N[i] = N [ i - 1] + N[i - 2];
}
return N[n];
}
}
``````

The top down approach is showed as following.
In the top down approach, we actually consider from the top, which is `stair level n`. And the recursive equation is still `N[i] = N[i - 1] + N[i - 2]`. Hence we get the so-called optimal substructures in `Dynamic programming`. Thus, by recursively calculate each level from `n` to base case, which is `0` and `1` and memorize the intermediate, we can still get the total number of distinct ways to go to stair `n`.

``````/*
top-down approach
*/

public int climbStairs(int n) {
int[] N = new int[n];
for (int i = 0; i < n; i++){
N[i] = -1;
}

}

private int topdownclimbStairs(int n, int[] N){
if (n == 0 || n == 1){
return 1;
}

if (N[n - 1] >= 0){
return N[n - 1];
}

else {
N[n - 1] = topdownclimbStairs(n-1, N) + topdownclimbStairs(n - 2, N);
return N[n - 1];
}
}
``````

• Thanks for your share！It is what i need

• This should return 0 if n is == 0. There are 0 ways to climb a set of stairs 0 steps high.

• Yes, that's reasonable. However, I return 1 because that is what returned by latched system. You can test this by using 0 as the test case.

• An explanation would be nice