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 { public int climbStairs(int n) { // Start typing your Java solution below // DO NOT write main() function int f0 = 0,f1= 1; int result = 0; for(int i = 0; i< n; i++){ result = f0 + f1; f0 = f1; f1 = result ; } return result; } }
public class Solution { public int climbStairs(int n) { int[] result = new int[3]; result[0] = 1; result[1] = 1; for(int i=2; i <= n;i++){ result[i%3] = result[(i-1)%3] + result[(i-2)%3]; } return result[n%3]; } }
learned: save space in dp
class Solution { /** * @param n: an integer * @return an integer f(n) */ public int fibonacci(int n) { // write your code here if(n == 1)return 0; if(n == 2)return 1; int n1 = 0; int n2 = 1; int result = 0; for(int i = 3; i <= n ;i++){ result = n1 + n2; n1 = n2; n2 = result; } return result; } }
python: class Solution: # @param n, an integer # @return an integer def climbStairs(self, n): a = [] a.append(1) a.append(1) for i in range(2,n+1): a.append(a[i-1]+a[i-2]) return a[n]