这是一个创建于 2662 天前的主题，其中的信息可能已经有所发展或是发生改变。
题目
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入：2 输出：2 解释： 有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶 示例 2：
输入：3 输出：3 解释： 有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶 题解
这个题目只要模拟一下基本就能想到是 DP，状态方程写出来就是斐波那契数列。 dp[i] = dp[i-1] + dp[i-2] i-1 的时候跳一步可以到达 i i-2 的时候跳一步是 i-1，这个变成 dp[i-1]的子问题了,直接跳两步可以到达 i
java
class Solution { public int climbStairs(int n) { int[] dp = new int[n + 1]; dp[0] = 1; dp[1] = 1; for (int i = 2; i <= n; i++){ dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; } } python
class Solution: def climbStairs(self, n): """ :type n: int :rtype: int """ dp = [1 for i in range(n + 1)] for i in range(2, n+1): dp[i] = dp[i-1] + dp[i-2] return dp[n] 热门文章
 | 1 20015jjw 2018-09-25 00:43:35 +08:00 via Android 这题解法也不够好 空间上可以 O(1)的 |
 | 2 rabbbit 2018-09-25 00:51:33 +08:00 var climbStairs = function (n) { let sqrt5 = Math.sqrt(5); let result = (Math.pow(((1 + sqrt5) / 2), n + 1) - Math.pow(((1 - sqrt5) / 2), n + 1)) / sqrt5; return Number(result.toFixed()); }; O(1) |
 | 3 wwwaaa 2018-09-25 01:18:07 +08:00 via Android 能问下什么是 DP 嘛 |
 | 6 XiaoxiaoPu 2018-09-25 01:57:41 +08:00 @aenon 乘方的计算并不是 O(1)，浮点运算的误差累积导致结果有可能有偏差，浮点运算相比整数加法要慢得多 |
 | 8 NVDA 2018-09-25 02:26:44 +08:00 via iPhone 本来想说这种东西放到题目下面的 discussion 就可以了，往上一划发现有个二维码，好吧\_(ツ)_/ |
 | 9 layorlayor 2018-09-25 10:12:36 +08:00 那进阶一下，n<=1e18， 结果对 1e9+7 取模 |
 | 10 earendil1412 2018-09-25 10:19:51 +08:00 via Android @XiaoxiaoPu 可以用矩阵来算[[1,1],[1,0]]的 n 次方 |
 | 11 IceSolStice 2018-09-25 10:31:05 +08:00 这不是就是斐波那契数列么 = = |
| 12 IceSolStice 2018-09-25 11:13:22 +08:00 递归的方法不好，因为存在大量重复计算。比如在计算 dp[5] = dp[4]+dp[3], 其中计算 dp[4] = dp[3]+dp[2]。发现其实 dp[3]计算了两次，数值越大，重复计算次数越多。两种解决方案，一是递归的时候记录 如果有过 dp[i], 直接返回。否则计算 dp[i]。二是用递推，从 1 推到 n，而不是从 n 递归到 1 |
Select Language