问题描述
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 step + 1 step
- 2 steps Example 2:
Input: 3 Output: 3 Explanation: There are three ways to climb to the top.
- 1 step + 1 step + 1 step
- 1 step + 2 steps
- 2 steps + 1 step
解决思路
动态规划不太会。感觉就是和递归倒过来，但是通过循环，避免了大量的内存消耗。试图解释一下吧：
- 初始状态：第1个台阶，1种；第2个台阶，2种。
- 动态方程： 当前台阶方法数 = 前一个台阶方法数 + 前前一个台阶方法数
代码一（DP）
package leetcode;
public class ClimbingStairs {
public int climbStairs(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
int current = 2;
int prev = 1;
int newCurrent = 0, newPrev = 0;
for (int i = 3; i <= n; i++) {
newCurrent = current + prev;
newPrev = newCurrent - prev;
current = newCurrent;
prev = newPrev;
}
return current;
}
}
代码二（递归，Time out）
package leetcode;
public class ClimbingStairs {
public int climbStairs(int n) {
if (n == 1 || n == 0 ){
return 1;
}
return climbStairs(n -1 ) + climbStairs(n - 2);
}
}
