这个题目是一个计算n层阶梯情况下，走到顶端的路径种数（要求每次只能上1层或者2层阶梯）。
这是一个动态规划的题目：
n = 1 时 ways = 1；
n = 2 时 ways = 2；
n = 3 时 ways = 3；
…
n = k 时 ways = ways[k-1] + ways[k-2]；
明显的，这是著名的斐波那契数列问题。有递归和非递归两种方式求解，但是亲测递归方式会出现 The Time Limit异常，所以只能采用非递归计算，可以用一个动态数组保存结果。数组的前三个不遵循规律，所以单独列出。Fibonacci number is: 1, 1, 2, 3, 5... when counted from 1.
So the return result for n here should be the (n+1)th Fibonacci number.
public class Solution {
public int climbStairs(int n) {
if(n == 0 || n == 1 || n == 2) {
return n;
}
int[] res = new int[n + 1];
res[0] = 0;
res[1] = 1;
res[2] = 2;
for(int i = 3; i <= n; i++) {
res[i] = res[i-1] + res[i-2];
}
return res[n];
}
}
Shawngbk
commented
7 years ago
这个题目是一个计算n层阶梯情况下，走到顶端的路径种数（要求每次只能上1层或者2层阶梯）。 这是一个动态规划的题目： n = 1 时 ways = 1； n = 2 时 ways = 2； n = 3 时 ways = 3； … n = k 时 ways = ways[k-1] + ways[k-2]；
明显的，这是著名的斐波那契数列问题。有递归和非递归两种方式求解，但是亲测递归方式会出现 The Time Limit异常，所以只能采用非递归计算，可以用一个动态数组保存结果。数组的前三个不遵循规律，所以单独列出。Fibonacci number is: 1, 1, 2, 3, 5... when counted from 1. So the return result for n here should be the (n+1)th Fibonacci number.
public class Solution { public int climbStairs(int n) { if(n == 0 || n == 1 || n == 2) { return n; } int[] res = new int[n + 1]; res[0] = 0; res[1] = 1; res[2] = 2; for(int i = 3; i <= n; i++) { res[i] = res[i-1] + res[i-2]; } return res[n]; } }