LeetCode 题解:70. 爬楼梯,DP 遍历数组,JavaScript,详细注释
原题链接:https://leetcode-cn.com/problems/climbing-stairs/
解题思路:
该题其实就是求解斐波那契数列,可以参考题解【手绘图解】从递归到动态规划,该题解给出的是动态规划解,下面是动态规划的遍历数组解法。
```javascript []
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function (n) {
// 创建一个长度为n+1的数组存放结果
let dp = new Array(n + 1).fill(0);
// 遍历数组,不断计算f(n)=f(n-1)+f(n-2),并累加结果
// 数组的最后一位则为最终结果
for (let i = 0; i < dp.length; i++) {
// i<3时,其步数与i相同,可以直接存放
if (i < 3) {
dp[i] = i;
}
// i>3时,当前结果为i-1与i-2之和
else {
dp[i] = dp[i - 1] + dp[i - 2];
}
}
return dp[dp.length - 1];
};
```
版权声明: 本文为 InfoQ 作者【Lee Chen】的原创文章。
原文链接:【http://xie.infoq.cn/article/798e611d355664e8d28816cfe】。文章转载请联系作者。
评论