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
LeetCode上的原题,请参见我之前的博客Climbing Stairs。
解法一:
class Solution { public: /** * @param n: An integer * @return: An integer */ int climbStairs(int n) { ) ; vector<int> dp(n); dp[] = ; dp[] = ; ; i < n; ++i) { dp[i] = dp[i - ] + dp[i - ]; } return dp.back(); } };
解法二:
class Solution { public: /** * @param n: An integer * @return: An integer */ int climbStairs(int n) { , b = ; while (n--) { b += a; a = b - a; } return a; } };