2013.12.22 04:13

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?

Solution:

　　Search for "" and calculate the nth element in the sequence.

　　Time complexity is O(n), space complexity is O(1).

Accepted code:

1 class Solution { 2 public: 3     int climbStairs(int n) { 4         // Note: The Solution object is instantiated only once and is reused by each test case. 5         int f1, f2, f3; 6          7         f1 = 0; 8         f2 = 1; 9         10         if(n <= 0){11             return 0;12         }13         14         for(int i = 0; i < n; ++i){15             f3 = f1 + f2;16             f1 = f2;17             f2 = f3;18         }19         20         return f3;21     }22 };