題目
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?
Note: Given n will be a positive integer.
Example 1:
Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1.1 step + 1 step
2.2 steps
Example 2:
Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1.1 step + 1 step + 1 step
2.1 step + 2 steps
3.2 steps + 1 step
解析
題目意思是比較好理解的，是一個(gè)正數(shù)n中，只有1和2兩種累加趾浅，求解多少種方法，不妨先用數(shù)學(xué)推導(dǎo)一下被因。
n????ways
1????1
2????2
3????3
4????5
...
n????F(n)
當(dāng)n=4時(shí)，其情況有
1,1,1,1
1,1,2
1,2,1
2,1,1
2,2
共5種情況
因此，F(xiàn)(n) = F(n-1) + F(n-2)呈础，意義是塌碌，F(xiàn)(n)是由第n-1階走1步和第n-2階走2步上來渊胸，兩種情況的累加。這是斐波那契數(shù)列台妆。再編寫代碼就很簡單了翎猛。
代碼
int climbStairs(int n) {
if (n == 1 || n == 2)
return n;
int prior = 1, behind = 2, ways = 0;
for (int i = 3; i <= n; ++i) {
ways = prior + behind;
prior = behind;
behind = ways;
}
return ways;
}
n=1和n=2的情況直接返回n1和2。從3開始接剩，設(shè)置prior為F(n-2)切厘，behind為F(n-1)，依次賦值懊缺，最終得到ways方式數(shù)量疫稿。
