Description
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.
Solution
非常基础的动态规划题。
DP
dp[i]表示跳上第i级台阶有多少种方式。那么dp[i + 1] = dp[i] + dp[i - 1]。
public class Solution {
public int climbStairs(int n) {
int[] ways = new int[n + 1];
ways[0] = 1;
ways[1] = 1;
for (int i = 2; i <= n; ++i) ways[i] = ways[i - 1] + ways[i - 2];
return ways[n];
}
}
DP with constant space
因为其实只需要记录prev以及prev.prev的值就可以了，用两个变量存储足矣。
public class Solution {
public int climbStairs(int n) {
int curr = 1, prev = 1;
while (--n > 0) {
int tmp = curr;
curr += prev;
prev = tmp;
}
return curr;
}
}
更简化的版本，不需要tmp变量。
public class Solution {
public int climbStairs(int n) {
int curr = 1, prev = 1;
while (--n > 0) prev = (curr += prev) - prev;
return curr;
}
}
