看到这个觉得这个问题应该是一个经典问题。
于是就想通过动态规划，从最后一步开始，不断递归解决问题，于是用很短的代码就把这个实现了。但是。。发现如果数字太大（到 44），因为复杂度太高（应该是 2^n），算法直接超时，所以还需要继续改进。
1
2
3
4
5
6
7
8
9
| class Solution {
public int climbStairs(int n) {
if(n<=2)
return n;
else{
return climbStairs(n-1)+climbStairs(n-2);
}
}
}
|
因为在递归的过程中，可能会计算很多类似的结果，所以可以将一些结果进行缓存，需要的时候直接查表，击败了 33.37%的人。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public int climb(int n,int[] store){
if(n<=2)
return n;
else{
if(store[n-1]>0)
return store[n-1];
else{
int stepCount=climb(n-1,store)+climb(n-2,store);
store[n-1]=stepCount;
return stepCount;
}
}
}
public int climbStairs(int n) {
int[] store=new int[n];
return climb(n,store);
}
}
|
看了官方 Solution 以后，大概明白动态规划还可以正着写（手动捂脸），只要知道之前的步骤的结果，就可以知道后面的结果。所以可以像斐波那契数列一样，定下前两个，根据stair[n]=stair[n-1]+stair[n-2]这个递推公式从前往后进行计算。（当然，更作弊的方法就是直接用斐波那契数列的求和公式，这里就没必要写出代码了）
其实这个方法和上面方法的复杂度一样，所以耗时也基本类似。（当然使用这个方法可以进一步去掉数组，只用两个变量代替，这样更加降低了算法的空间占用）
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public int climbStairs(int n) {
if(n==1)
return 1;
int[] stair=new int[n+1];
stair[1]=1;
stair[2]=2;
for(int i=3;i<=n;i++){
stair[i]=stair[i-1]+stair[i-2];
}
return stair[n];
}
}
|