题目
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
解法思路（一）
- 如果台阶数为 1，那么有 1 种不同的方式爬上来；
- 如果台阶数为 2，那么有 2 种不同的方式爬上来；
- 如果台阶数为 3，那么可以从 1 阶或 2 阶的地方爬上来，爬到 3 阶的不同方法就有：爬到 1 阶的不同方法 + 爬到 2 阶的不同方法；
- 如果台阶数为 n，那么可以从 n - 1 阶或 n - 2 阶的地方爬上来，爬到 n 阶的不同方法就有：爬到 n - 1 阶的不同方法 + 爬到 n - 2 阶的不同方法；
- 这就很斐波那契了；
解法实现（一）
关键字
递归 斐波那契 爬梯子
实现细节
- 递归实现，超时；
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));
}
}
解法实现（二）
关键字
记忆化的递归 斐波那契 爬梯子
实现细节
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);
}
}
解法实现（三）
关键字
动态规划 自底向上 斐波那契 爬梯子
实现细节
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];
}
}
