爬楼梯问题 |
您所在的位置：网站首页 › 三年级爬楼梯问题 › 爬楼梯问题 |
爬楼梯问题
|
方法一：动态规划
思路和算法
用 f ( x ) f(x) f(x)表示爬到第 x 级台阶的方案数。 最后一步可能跨了一级台阶，也可能跨了两级台阶，所以： f ( x ) = f ( x − 1 ) + f ( x − 2 ) f(x)=f(x−1)+f(x−2) f(x)=f(x−1)+f(x−2) 它意味着爬到第 x 级台阶的方案数是爬到第 x−1 级台阶的方案数和爬到第 x−2级台阶的方案数的和。很好理解，因为每次只能爬 1 级或2级，所以 f(x)只能从 f(x−1)和 f(x−2)转移过来，而这里要统计方案总数，我们就需要对这两项的贡献求和。 边界条件 f ( 0 ) = 1 , f ( 1 ) = 1 f(0)=1 , f(1)=1 f(0)=1,f(1)=1 我们是从第 0 级开始爬的，所以从第 0级爬到第 0级我们可以看作只有一种方案，即f(0)=1；从第 0 级到第 1 级也只有一种方案，即爬一级，f(1)=1。 这两个作为边界条件就可以继续向后推导出第 n级的正确结果。我们不妨写几项来验证一下，根据转移方程得到f(2)=2，f(3)=3，f(4)=5…我们把这些情况都枚举出来，发现计算的结果是正确的。 我们不难通过转移方程和边界条件给出一个时间复杂度和空间复杂度都是 O ( n ) O(n) O(n)的实现，但是由于这里的 f ( x ) f(x) f(x)只和 f ( x − 1 ) f(x−1) f(x−1) 与 f ( x − 2 ) f(x−2) f(x−2)有关，所以我们可以用滚动数组思想把空间复杂度优化成 O ( 1 ) O(1) O(1)。下面的代码中给出的就是这种实现。
如何想到使用矩阵快速幂？ 如果一个问题可与转化为求解一个矩阵的 n次方的形式，那么可以用快速幂来加速计算如果一个递归式形如 f ( n ) = ∑ i = 1 m a i f ( n − i ) f(n) = \sum_{i = 1}^{m} a_i f(n - i) f(n)=∑i=1maif(n−i)，即齐次线性递推式，我们就可以把数列的递推关系转化为矩阵的递推关系，即构造出一个矩阵的 n 次方乘以一个列向量得到一个列向量，这个列向量中包含我们要求的 f(n) A n × 列 向 量 = 列 向 量 A^n \times 列向量 = 列向量 An×列向量=列向量一般情况下，形如 f ( n ) = ∑ i = 1 m a i f ( n − i ) f(n) = \sum_{i = 1}^{m} a_i f(n-i) f(n)=∑i=1maif(n−i)可以构造出这样的 m × m m \times m m×m 的矩阵：第一行为 a i a_i ai，下面为单位矩阵。 [ a 1 a 2 a 3 ⋯ a m 1 0 0 ⋯ 0 0 1 0 ⋯ 0 0 0 1 ⋯ 0 ⋮ ⋮ ⋮ ⋱ ⋮ 0 0 0 ⋯ 1 ] \left[ \begin{matrix} a_1 & a_2 & a_3 & \cdots & a_m \\ 1 & 0 & 0 & \cdots & 0 \\ 0 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & 1 \\ \end{matrix} \right] ⎣⎢⎢⎢⎢⎢⎢⎢⎡a1100⋮0a2010⋮0a3001⋮0⋯⋯⋯⋯⋱⋯am000⋮1⎦⎥⎥⎥⎥⎥⎥⎥⎤有些时候我们可以把非齐次线性递推转化为其次线性递推，比如这样一个递推： f ( x ) = ( 2 x − 6 ) c + f ( x − 1 ) + f ( x − 2 ) + f ( x − 3 ) f(x) = (2x-6)c + f(x - 1) + f(x - 2) + f(x - 3) f(x)=(2x−6)c+f(x−1)+f(x−2)+f(x−3) 我们可以做这样的变换： f ( x ) + x c = [ f ( x − 1 ) + ( x − 1 ) c ] + [ f ( x − 2 ) + ( x − 2 ) c ] + [ f ( x − 3 ) + ( x − 3 ) c ] f(x) + xc = [f(x - 1) + (x - 1)c] + [f(x - 2) + (x - 2)c] + [f(x - 3) + (x - 3)c] f(x)+xc=[f(x−1)+(x−1)c]+[f(x−2)+(x−2)c]+[f(x−3)+(x−3)c] 令 g ( x ) = f ( x ) + x c g(x)=f(x)+xc g(x)=f(x)+xc，那么我们又得到了一个齐次线性递： g ( x ) = g ( x − 1 ) + g ( x − 2 ) + g ( x − 3 ) g(x)=g(x−1)+g(x−2)+g(x−3) g(x)=g(x−1)+g(x−2)+g(x−3) 于是就可以使用矩阵快速幂求解了。 所有非齐次线性都可以化成齐次线性。 代码 public class Solution { public int climbStairs(int n) { int[][] q = {{1, 1}, {1, 0}}; int[][] res = pow(q, n); return res[0][0]; } #矩阵快速幂算法 public int[][] pow(int[][] a, int n) { int[][] ret = {{1, 0}, {0, 1}}; while (n > 0) { if ((n & 1) == 1) { ret = multiply(ret, a); } n >>= 1; a = multiply(a, a); } return ret; } #矩阵乘法定义（固定维数） public int[][] multiply(int[][] a, int[][] b) { int[][] c = new int[2][2]; for (int i = 0; i < 2; i++) { for (int j = 0; j < 2; j++) { c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j]; } } return c; } }复杂度 时间复杂度：同快速幂，O(logn)。 空间复杂度：O(1)。 方法三：通项公式 思路之前的方法我们已经讨论了 f ( n ) f(n) f(n)是齐次线性递推，根据递推方程 f ( n ) = f ( n − 1 ) + f ( n − 2 ) f(n)=f(n−1)+f(n−2) f(n)=f(n−1)+f(n−2)，我们可以写出这样的特征方程： x 2 = x + 1 x^2 = x + 1 x2=x+1 求得 x 1 = 1 + 5 2 x_1 = \frac{1+\sqrt{5}}{2} x1=21+5 ， x 2 = 1 − 5 2 x_2 = \frac{1-\sqrt{5}}{2} x2=21−5 设通解为 f ( n ) = c 1 x 1 n + c 2 x 2 n f(n) = c_1 x_1 ^n + c_2 x_2 ^ n f(n)=c1x1n+c2x2n，代入初始条件 f(1)=1，f(2)=1 得 c 1 = 1 5 c_1 = \frac{1}{\sqrt{5}} c1=5 1， c 2 = − 1 5 c_2 = -\frac{1}{\sqrt{5}} c2=−5 1，我们得到了这个递推数列的通项公式： f ( n ) = 1 5 [ ( 1 + 5 2 ) n − ( 1 − 5 2 ) n ] f(n) = \frac{1}{\sqrt{5}}\left[ \left(\frac{1+\sqrt{5}}{2}\right)^{n} - \left(\frac{1-\sqrt{5}}{2}\right)^{n} \right] f(n)=5 1[(21+5 )n−(21−5 )n] 接着我们就可以通过这个公式直接求第 n项了。 代码 public class Solution { public int climbStairs(int n) { double sqrt5 = Math.sqrt(5); double fibn = Math.pow((1 + sqrt5) / 2, n + 1) - Math.pow((1 - sqrt5) / 2, n + 1); return (int)(fibn / sqrt5); } }复杂度 时间复杂度：O(log n)，pow 方法将会用去 O(logn)的时间。 空间复杂度：O(1)。 总结这里形成的数列正好是斐波那契数列，答案要求的 f(n)即是斐波那契数列的第 n 项（下标从 0 开始）。我们来总结一下斐波那契数列第 n 项的求解方法： n比较小的时候，可以直接使用过递归法求解，不做任何记忆化操作，时间复杂度是 O(2n)，存在很多冗余计算。一般情况下，我们使用「记忆化搜索」或者「迭代」的方法，实现这个转移方程，时间复杂度和空间复杂度都可以做到 O(n)。为了优化空间复杂度，我们可以不用保存 f ( x − 2 ) f(x-2) f(x−2)之前的项，我们只用三个变量来维护 f ( x ) f(x) f(x)、 f ( x − 1 ) f(x−1) f(x−1)和 f ( x − 2 ) f(x−2) f(x−2)，你可以理解成是把「滚动数组思想」应用在了动态规划中，也可以理解成是一种递推，这样把空间复杂度优化到了O(1)。随着 n的不断增大 O(n) 可能已经不能满足我们的需要了，我们可以用「矩阵快速幂」的方法把算法加速到 O(logn)。我们也可以把 n 代入斐波那契数列的通项公式计算结果，但是如果我们用浮点数计算来实现，可能会产生精度误差。作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/climbing-stairs/solution/pa-lou-ti-by-leetcode-solution/ 来源：力扣（LeetCode） |
【本文地址】
今日新闻 |
推荐新闻 |