70.（动态规划）爬楼梯

解决方法1:递归+记忆搜索

/**
 * @param {number} n
 * @return {number}
 */
//爬n阶台阶可以分成两种
//1.爬n-1阶台阶，再爬1阶
//2.爬n-2阶台阶，再爬2阶

//有很多重复的，比如爬n-1阶台阶，就可以分为爬n-2阶台阶再爬1阶，和爬n-3阶台阶再爬两阶。像爬n-2阶台阶就已经用过了
//所以可以使用记忆搜索算法
//也就是使用一个n维数组，arr[n-1]=爬n阶台阶的数目，因为索引是从0开始的
 
  
var climbStairs = function(n) {

    arr=[];
 //给数组所有值初始化为-1
    for(let i=0;i<n;i++)
        arr.push(-1);
   
    return calcWays(n,arr);
};

function calcWays(num){
    //如果爬1阶台阶就是1种
    if(num===1)
        return 1;
    //如果爬2阶台阶，有两种爬法
    if(num===2)
        return 2;
    
    if(arr[num-1]===-1){
        arr[num-1]=calcWays(num-1)+calcWays(num-2);
    }
       
    
    return arr[num-1];
}

使用动态规划

class Solution {
    public int climbStairs(int n) {
        //用动态规划实现
        //第n个的台阶数总是n-1，n-2的台阶数之和
        int []memo=new int[n+1];
        memo[0]=1;
        memo[1]=1;
        for(int i=2;i<memo.length;i++){
            memo[i]=memo[i-1]+memo[i-2];
        }
        
        return memo[n];
    }
}