跳转至

爬楼梯问题

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

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

简单题。

递归

class Solution:
    def climbStairs(self, n: int) -> int:
        mem = {1: 1, 2: 2}

        def dfs(n):
            if n in mem:
                return mem[n]
            else:
                res = dfs(n - 1) + dfs(n - 2)
                mem[n] = res
                return res

        return dfs(n)

使用递归求解最快，并且最直观。

本质上就是考虑第一步走1个台阶或者2个台阶。

动态规划

当然，我们可以把递归改成递推版本。

class Solution:
    def climbStairs(self, n: int) -> int:
        dp = [0, 1, 2]
        if n<=2:
            return dp[n]
        else:
            for i in range(n-2):
                dp.append(dp[-1]+dp[-2])
            return dp[-1]

这实际上就是一个非波拉契数列。

组合

我们也可以用组合数学直接给出答案。

本质上这题是求解不定方程：

$$ 2x + y = n $$

其中$x,y$都是自然数。

这个方程比较简单，显然有$1+\lfloor n/2 \rfloor $组解。

分别是 $$ x = 0, 1, \cdots, \lfloor n/2 \rfloor; \quad y = n-2x $$

而后只需要对$x$个2和$y$个1进行排列组合即可。

相当于一共$n-2x + x$个步伐，其中$x$个步伐是走两级台阶，$n-2x$个步伐是走1级台阶。

所有可能的组合数是： $$ C_{n-x}^x $$

所以最终的答案是： $$ \sum_{x=0}^{\lfloor n/2 \rfloor} C_{n-x}^x $$

def climbStairs(n: int) -> int:
    return sum(comb(n - x, x) for x in range(n // 2 + 1))

当然，这个式子或许可以化简一下。

实际上我们知道，非波拉契数列是有解析解的。不过这已经和算法无关了，我们不再继续往下做了。

最后更新: 2025-05-29 02:42:18
创建日期: 2025-04-17 21:54:37

评论