tag:
- Easy;
- Dynamic Programming;
question:
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
思路：
动态规划DP来做。这里我们定义一个一维的dp数组，其中dp[i]表示爬到第i层的方法数，然后我们来想dp[i]如何推导。我们来思考一下如何才能到第i层呢？是不是只有两种可能性，一个是从第i-2层上直接跳上来，一个是从第i-1层上跳上来。不会再有别的方法，所以我们的dp[i]只和前两层有关系，所以可以写做如下：
dp[i] = dp[i- 2] + dp[i - 1]
最后我们返回最后一个数字dp[n]即可，节省空间只需三个变量就行，参见代码如下：
class Solution {
public:
int climbStairs(int n) {
if (n==1)
return 1;
if (n==2)
return 2;
int a=1, b=2;
int res = 0;
for (int i=3; i<=n; ++i) {
res = a + b;
a = b;
b = res;
}
return res;
}
};
