斐波那契数列经典算法题：爬梯子的N种方式

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

比如：

n = 2，结果有两种：
1 + 1
2

n = 3，结果有三种：
1 + 1 + 1
1 + 2
2 + 1

其实只要算出后面的结果，就能清楚这就是一个斐波那契数列，公式为：f(n) = f(n-1) + f(n-2)，用通俗的话来说就是当前结果等于上两层相加的结果

使用 PHP 来实现算法逻辑：

function climbStairs(int $n) : int {
    if ($n <= 2) {
        return $n;
    }

    [$dp1, $dp2] = [1, 2];
    for ($i = 2; $i < $n; $i++) {
        [$dp1, $dp2] = [$dp2, $dp1 + $dp2];
    }
    return $dp2;
}

使用 Go 来实现算法逻辑：

func climbStairs(n int) int {
    if n <= 2 {
        return n
    }

    dp1, dp2 := 1, 2
    for i := 2; i < n; i++ {
        dp1, dp2 = dp2, dp1 + dp2
    }
    return dp2
}

使用 TypeScript 来实现算法逻辑：

function climbStairs(n: number) : number {
    if (n <= 2) {
        return n;
    }

    let dp1 = 1;
    let dp2 = 2;
    for (let i = 2; i < n; i++) {
        [dp1, dp2] = [dp2, dp1 + dp2];
    }
    return dp2;
}

后来想想这段逻辑其实可以优化成递归的方式更简便去实现：

function climbStairs(int $n) : int {
    if ($n <= 2) {
        return $n;
    }

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

Go 与 TypeScript 的实现方式与 PHP 大同小异，这里就不例举了

———————————————————————————————————————————

2023.6.14 后记：通过 Go 代码运行耗时比较，如果这个 n 的值很大，使用递归的方式就会非常耗时。因为每次递归的时候都需要再进行两次递归，具体次数则为 2 的 n 次方，再加上函数的作用域是在栈上，频繁入栈出栈也会损耗一定的时间，所以最佳方式还是一开始的那段实现逻辑。通过实践还是证明，优雅的解决方式不一定是性能最佳的，有时候不需要过度封装反而效果更好。

斐波那契数列经典算法题：爬梯子的N种方式

发表评论