爬楼梯

Tips

题目类型: Dynamic Programming, Recursive

题目

假设你正在爬楼梯. 需要 n 阶你才能到达楼顶. 每次你可以爬 1 或 2 个台阶. 你有多少种不同的方法可以爬到楼顶呢?

提示:

• 1 <= n <= 45

示例

输入: n = 2
输出: 2
解释: 有两种方法可以爬到楼顶.
1. 1 阶 + 1 阶
2. 2 阶

输入: n = 3
输出: 3
解释: 有三种方法可以爬到楼顶.
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

题解

JavaScript - 动态规划一维数组

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
  const dp = []

  dp[0] = 1
  dp[1] = 1

  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2]
  }
  
  return dp[n]
}

JavaScript - 动态规划

这道题跟求斐波那契数差不多, 只关心 n 的前两个状态, 因此不需要额外声明一个数组, 只要存储前两个值即可.

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
  if (n < 2) return n

  let prev = 1
  let curr = 1

  for (let i = 2; i <= n; i++) {
    const sum = prev + curr
    prev = curr
    curr = sum
  }

  return curr
}

Rust

pub fn climb_stairs(n: i32) -> i32 {
    let mut prev = 1;
    let mut curr = 1;

    for i in 2..=(n as usize) {
        let sum = prev + curr;
        prev = curr;
        curr = sum;
    }

    curr
}