Climbing Stairs
https://leetcode.com/problems/climbing-stairs/description/
Easy You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Thoughts
问有多少种想到DP. 和上题类似,到达i阶分别有从i - 1和i - 2两种方法, 因此设f(i)为在i阶的方法数,递推式f[i] = f[i - 1] + f[i - 2], 也就是斐波那契数列。
给定N,
设Fi为从0处往上爬一步或两步到i处的unique path的数目. 求F(N).
Code
class Solution {
public int climbStairs(int n) {
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
}
int[] f = new int[n];
f[0] = 1;
f[1] = 2;
for (int i = 2; i < n; i++) {
f[i] = f[i - 1] + f[i - 2];
}
return f[n - 1];
}
}
Analysis
做题耗时: 4min
时间复杂度为O(n), 空间复杂度也是O(n). 但我们观察到f[i]实际上只有i-1和i-2有关,完全不需要存整个数组。
Ver.2
class Solution {
public int climbStairs(int n) {
int[] f = new int[2];
f[0] = 2; f[1] = 1;
for (int i = 3; i <= n; i++) {
f[i % 2] = f[(i - 1) % 2] + f[(i - 2) % 2];
}
return f[n % 2];
}
}
Analysis
TC: O(n), SC: O(1)
Last updated
Was this helpful?