这是一个创建于 2270 天前的主题，其中的信息可能已经有所发展或是发生改变。
题目
假设你正在爬楼梯。需要 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
Mirage09 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
mbtfdwlx 2018-09-25 10:31:05 +08:00
这不是就是斐波那契数列么 = =
|
|
12
mbtfdwlx 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