You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

public class Solution {
/*Use Dynamic Programming*/
public int climbStairs(int n) {
if (n == 0 || n == 1)
return 1;
if (n == 2)
return 2;
//create an array to store # of ways of each step n
int[] array = new int[n];
//Base case: step = 0
array[0] = 1;
//Base case: step = 1
array[1] = 2;
//General case: use DP
for (int i = 2; i < n; i++) {
//At (i-1)th step, one can climb 1 more step to reach i.
//At (i-2)th step, one can climb 2 more step to reach i.
array[i] = array[i-1] + array[i-2];
}
return array[n-1];
}
}

### Like this:

Like Loading...

*Related*