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;
}
return topdownclimbStairs(n, N);
}
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];
}
}
```