Problem description
Level: easy
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?
Example
Given an example n=3 , 1+1+1=2+1=1+2=3
return 3
Analysis:
As it is asking for count #, we can consider trying DP
state: count how many distinct ways in position i use f(i)
Function: f(i) = f(i-1) + f(i-2) To climb to I, it can be from i-1 and i-2
Initialize: f(1) = 1 f(2) = 2
final: f(n)
Solution 1:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
public static int climbStairs(int n) { int[] f = new int[n + 1]; if (n == 1) { f[1] = 1; } if (n >= 2) { f[2] = 2; f[1] = 1; for (int i = 3; i < n + 1; i++) { f[i] = f[i - 1] + f[i - 2]; } } return f[n]; } |
Solution 2:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
public int climbStairs(int n) { int[] f = new int[n+1]; return helper(n, f); } public static int helper(int n, int[] f) { if(n == 1) { f[1] = 1; } else if(n == 2) { f[2] = 2; } else { if(f[n-1] == 0) { f[n-1] = helper(n-1, f); } if(f[n-2] == 0) { f[n-2] = helper(n-2, f); } f[n] = f[n-1] + f[n-2]; } return f[n]; } |
