題目
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:
Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1 step + 1 step
2 steps
Example 2:
Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1 step + 1 step + 1 step
1 step + 2 steps
2 steps + 1 step
解法思路（一）
- 如果臺階數(shù)為 1惶翻，那么有 1 種不同的方式爬上來缆娃；
- 如果臺階數(shù)為 2犁享，那么有 2 種不同的方式爬上來；
- 如果臺階數(shù)為 3，那么可以從 1 階或 2 階的地方爬上來想邦，爬到 3 階的不同方法就有：爬到 1 階的不同方法 + 爬到 2 階的不同方法两残；
- 如果臺階數(shù)為 n永毅，那么可以從 n - 1 階或 n - 2 階的地方爬上來，爬到 n 階的不同方法就有：爬到 n - 1 階的不同方法 + 爬到 n - 2 階的不同方法人弓；
- 這就很斐波那契了卷雕；
解法實現(xiàn)（一）
關鍵字
遞歸 斐波那契 爬梯子
實現(xiàn)細節(jié)
- 遞歸實現(xiàn)，超時票从；
package leetcode._70;
public class Solution70_1 {
public int climbStairs(int n) {
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
return climbStairs(n - 1) + climbStairs(n - 2);
}
public static void main(String[] args) {
Solution70_1 solution = new Solution70_1();
System.out.println(solution.climbStairs(4));
}
}
解法實現(xiàn)（二）
關鍵字
記憶化的遞歸 斐波那契 爬梯子
實現(xiàn)細節(jié)
package leetcode._70;
import java.util.Arrays;
public class Solution70_2 {
private int[] memo;
public int climbStairs(int n) {
memo = new int[n + 1];
Arrays.fill(memo, -1);
return calculateStairs(n);
}
private int calculateStairs(int n) {
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
if (memo[n] == -1) {
memo[n] = calculateStairs(n - 1) + calculateStairs(n - 2);
}
return memo[n];
}
public static void main(String[] args) {
Solution70_2 solution = new Solution70_2();
int res = solution.climbStairs(3);
System.out.println(res);
}
}
解法實現(xiàn)（三）
關鍵字
動態(tài)規(guī)劃 自底向上 斐波那契 爬梯子
實現(xiàn)細節(jié)
package leetcode._70;
public class Solution70_3 {
public int climbStairs(int n) {
int[] memo = new int[n + 1];
memo[0] = 1;
memo[1] = 1;
for(int i = 2 ; i <= n ; i ++)
memo[i] = memo[i - 1] + memo[i - 2];
return memo[n];
}
}
