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?
递推公式为f(n)=f(n-1)+f(n-2)
每个元素仅依赖于前两个元素。
1 class Solution { 2 public: 3 int climbStairs(int n) { 4 int result[3] = {0,1,2}; 5 if(n < 3){ 6 return result[n]; 7 } 8 9 int f1 = 1; 10 int f2 = 2; 11 int fn = 0; 12 13 for(int i = 3; i <= n; i++ ){ 14 fn = f1 + f2; 15 f1 = f2; 16 f2 = fn; 17 } 18 return fn; 19 } 20 };
原文：http://www.cnblogs.com/sankexin/p/5874689.html