LintCode (111) Climbing Stairs Show result

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?

Have you met this question in a real interview? 

Yes

Example

Given an example n=3 , 1+1+1=2+1=1+2=3

return 3

斐波切那函数的变种题目。。。。难为出题的人了。。。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

class Solution { public: /** * @param n: An integer * @return: An integer */ int climbStairs(int n) { // write your code here if (n==1) return 1; int prev=1; int cur=2; for(int i=3; i<=n; i++){ int prepre=prev; prev=cur; cur=prepre+prev; } return cur; } };