Leetcode Algorithm 070. Climbing Stairs
Climbing Stairs 有一条n级的楼梯，每次只能走一级或两级，求总共有多少级走法
解题思路
用f[i]表示走到第i级的时候的走法，那么我们只可能从第i-1级走一步或者从i-2级走两步到达第i级，故有一条状态转移方程式： f[i] = f[i-1] + f[i-2]。
边界情况有：f[0] = 0; f[1] = 1; f[2] = 2;
可以发现这条状态转移方程类似斐波那契数列，可以用递归法或者迭代法来求解。下面给出迭代法的解法。
代码
#include<iostream>
using namespace std;
class Solution {
public:
int climbStairs(
int n) {
int f1 =
1;
int f2 =
2;
if (n ==
0)
return 0;
else if (n ==
1)
return f1;
else if (n ==
2)
return f2;
else {
int fn;
while (n >
2) {
fn = f1 + f2;
f1 = f2;
f2 = fn;
n--;
}
return fn;
}
}
};
测试样例
int main() {
Solution s;
cout << s.climbStairs(
3) << endl;
cout << s.climbStairs(
44) << endl;
return 0;
}
输出
3
1134903170
