Skip to content

LeetCode题解:70. 爬楼梯,DP遍历数组,JavaScript,详细注释 #118

@chencl1986

Description

@chencl1986

原题链接:https://leetcode-cn.com/problems/climbing-stairs/

解题思路:

该题其实就是求解斐波那契数列,可以参考题解【手绘图解】从递归到动态规划,该题解给出的是动态规划解,下面是动态规划的遍历数组解法。

/**
 * @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];
};

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions