【LeetCode 0070】【递归/动态规划】爬楼梯

70. Climbing Stairs

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:

**Input:** n = 2
**Output:** 2
**Explanation:** There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

**Input:** n = 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

Constraints:

• 1 <= n <= 45

Idea

根据题目描述，每次走动只能在一步到两步当中选。
到达第N阶梯，要么从第n-1阶梯一步到第n阶梯；要么从第n-2两步到第n阶梯
设T(n)为到第n阶梯的走法种数，则T(n)=T(n-1)+T(n-2)
边界考虑：n约束在大于0范围内
当n=1时，只有一种走法T(1)=1
当n=2时，要么1+1，要么2 ，即T(2)=2
当n>2时，T(n)=T(n-1)+T(n-2)

JavaScript Solution

• 解法一，自顶向下的递归（存在重复计算问题,一般需要额外记录存储空间）

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    if(n < 3){
    	return n;
    }
    return climbStairs(n-1) + climbStairs(n-2)
};

• 解法二，自底向上的迭代（简易动态规划）–更优

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
	if(n < 3){
    	return n;
    }
    let [prev, result] = [1, 2];
    for(let i = 3; i <= n; i++ ){
    	//利用EC6 语法糖简写,减少中间变量声明
    	[prev,result] = [result,result+prev]
    }
    return result
};