05 August 2008
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?
Note: Given n will be a positive integer.
Example 1:
1
2
3
4
5
Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Example 2:
1
2
3
4
5
6
Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
爬梯子，每次爬一步或者两步，总共有多少种爬法。虽然是简单题，但是一道极佳的说明动态规划的题目，想法类似于斐波那契数列。
以空间换时间，空间复杂度为O(n), dp[i] = dp[i - 2] + dp[i - 2]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public int climbStairs(int n) {
if (n == 1) { //防止下面的dp array越界
return 1;
}
int result = 0;
int[] dp = new int[n + 1];
// dp[0] 跳过不计算
dp[1] = 1; // n等于1步的时候
dp[2] = 2; // n等于2步的时候
for (int i = 3; i <= n; i++) { //包括n
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
数组的长度是否+1可以是比较灵活的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
// dp[n] = dp[n - 1] + dp[n - 2]
public int climbStairs(int n) {
if (n == 1) {
return 1;
}
int[] dp = new int[n];
// dp[0] 不跳过
dp[0] = 1; // n等于1步的时候
dp[1] = 2; // n等于2步的时候
for (int i = 2; i < n; i++) { // 从0开始这里就不用等于了
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n - 1]; //返回最后一个
}
}
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public int climbStairs(int n) {
int[] dp = new int[n + 2]; //舍弃掉最前面的一个空位，好记，第i个元素就是第i步梯子
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
优化一下空间，只需存最后两步即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int climbStairs(int n) {
if (n <= 0) {
return 0;
}
if (n == 1) {
return 1;
}
int twoStepsBefore = 1;
int oneStepBefore = 2;
for (int i = 3; i <= n; i++) {
int temp = twoStepsBefore + oneStepBefore;
twoStepsBefore = oneStepBefore;
oneStepBefore = temp;
}
return oneStepBefore;
}
}