70. Climbing Stairs
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?
思考：
| top | steps |
| 1 | 1 |
| 2 |
2 |
| 3 |
3 |
| 4 |
5 |
| 5 |
8 |
| 6 |
13 |
| ... |
... |
使用动态规划，确定当前登到第i级台阶可能的步数是几。然后在查看下一级i+1台阶的可能步数。
代码实现如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class
Solution {
public
:
int
climbStairs(
int
n)
{
if
(n <= 0)
return
0;
if
(n <= 2)
return
n;
int
a[2] = {1,2};
int
tmp = 0;
for
(
int
i = 0; i < n - 2; ++i)
{
tmp = a[0] + a[1];
a[0] = a[1];
a[1] = tmp;
}
return
tmp;
}
};
|
总结：
先确定当前的结果，然后转移。确定下一步的结果。依次转移，直到结果。
本文转自313119992 51CTO博客，原文链接:http://blog.51cto.com/qiaopeng688/1844815
