提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

Leetcode 题目070-爬楼梯

LeetCode 题目 爬楼梯
2023-06-13 09:13:08 时间

我们用 f(n) 表示爬到第 n 级台阶的方案数，考虑最后一步可能跨了一级台阶，也可能跨了两级台阶，所以我们可以列出如下递归公式：

f(n) = f(n−1)+f(n−2)

并且 显然有

f(1) = 1,

f(2) = 2。

（还可以反推 f(0) = f(2) -f(1) =1, 完全契合 斐波那契数列）

  • 最容易想到的的算法是递归, 缺点是效率低
class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1: return 1
        if n == 2: return 2
        return self.climbStairs(n-1) + self.climbStairs(n-2)

提交后显示 计算 f(40) 超时， 果然效率低。

  • 这个递归很容易改造成循环
class Solution:
    def climbStairs(self, n: int) -> int:
        a, b = 1, 1 # for n==0 and n==1
        for i in range(1, n):
            a, b  = b, a+b # python 语法糖， 不用临时变量
        return b
  • 我们还可以直接求出通项公式

根据递归公式有

上式可以用写成矩阵乘法的形式：

记

，

则有

显然求 f(n) 问题转换为求

的 第二行的元素之和。

import numpy as np
class Solution:
    def climbStairs(self, n: int) -> int:
    # 这里偷懒借助numpy
        A = np.matrix([[1,1], [1,0]], dtype=int)
        B = A ** n
        return int(np.sum(B[1]))
  • 还可以由线性代数中 矩阵对角化的相关知识 简化

的计算

矩阵的对角化

由

解出两个特征值：

没有重根。

之后直接根据通项公式求解。

from math import sqrt
class Solution:
    def climbStairs(self, n: int) -> int:
        sqrt5 = sqrt(5)
        res  = ((1+sqrt5)/2.0)**(n+1) - ((1-sqrt5)/2.0)**(n+1)
        res = res/ sqrt5
        return int(res)

相关文章