解决方法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];
}
}
