假设你正在爬楼梯。需要 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
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];
}
}
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
|