爬楼梯 2022-02-25 周五

2022-02-25  本文已影响0人  勇往直前888

题目描述

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

解释:有两种方法可以爬到楼顶。

  1. 1 阶 + 1 阶
  2. 2 阶

解释:有三种方法可以爬到楼顶。

  1. 1 阶 + 1 阶 + 1 阶
  2. 1 阶 + 2 阶
  3. 2 阶 + 1 阶

学习文章

力扣官方视频

思路

递归

递归(C语言)

int climbStairs(int n) {
    if (n == 1) {
        return 1;
    }
    if (n == 2) {
        return 2;
    }

    return (climbStairs(n-1) + climbStairs(n-2));
}

结果应该是对的,但是不符合复杂度要求:


递归解法

滚动数组

递归的好处是理解起来简单,坏处是占用内存太多。递归对应的数据结构是栈。每计算一个,就要将前两个压栈,当n较大的时候,栈空间就用完了。
滚动数组只需要3个存储位置就好了。
原理其实很简单:
计算下一个的时候,当前的f(n-2)已经没用了,可以丢弃。所以通过移动的方式,将当前3个数字往前挪一位,然后计算前2个的和,放入第3个位置就可以了。

int climbStairs(int n) {
    // 边界条件
    if (n == 0) {
        return 1;
    }
    if (n == 1) {
        return 1;
    }
    if (n == 2) {
        return 2;
    }

    // n从3开始就通过滚动计算获得
    int target = 2;      // f(2)  f(n)
    int previous1 = 1;   // f(1)  f(n-1)
    int previous2 = 1;   // f(0)  f(n-2)

    // 滚动数组
    for (int i = 3; i <= n; i++) {
        // 现在f(n-1)就是下个数的f(n-2)
        previous2 = previous1; 

        // 现在f(n)就是下个数的f(n-1)
        previous1 = target; 

        // 执行公式f(n) = f(n-1) + f(n-2)
        target = previous1 + previous2;
    }

    // 返回结果
    return target;
}

力扣代码位置

JS的实现和C基本一样,不用贴了。把int 改为let就好了。当然性能还是10倍以上的差距。

上一篇 下一篇

猜你喜欢

热点阅读