假设你正在爬楼梯,需要n步你才能到达顶部。但每次你只能爬一步或者两步,你能有多少种不同的方法爬到楼顶部?
逆向思维,例如 n = 4
,那么他走的最后一步就只能是 1步
或者 2步
,
如果最后走的是1级台阶,那么之前走的就是3级台阶, 如果之前走的是2级台阶,那么之前走的就是2级台阶,
于是得到4阶台阶的走法就是3阶台阶的走法加上2阶台阶的走法。也就是3 + 2 = 5种。
如果还不明白的话 我这样看:
n=1:
n=2:
1+1
2
n=3:
1+1+1
1+2
2+1
n=4:
1+1+1+1
1+2+1
2+1+1
1+1+2
2+2
在原来的
n=3
的基础上,所有方法都加1步,变成了1+1+1+1
1+2+1
2+1+1
。 然后再在n=2
的基础上,所有方法都加2步,变成了1+1+2
2+2
然后在看看n=2
和n=3
的时候,分别加上2步和1步 就变成了n=4
的所有方法
public class Solution {
/**
* @param n: An integer
* @return: An integer
*/
public int climbStairs(int n) {
if (n == 1 || n == 2)
return n;
int now = climbStairs(n-2) + climbStairs(n-1);
return now;
}
}
递归方式虽然能实现这种,但是当n越大,程序运行时间就越长,最后还会导致
栈溢出
的情况,所以对算法进行了改进。
public class Solution {
/**
* @param n: An integer
* @return: An integer
*/
public int climbStairs(int n) {
if (n == 0) { //这里判断n == 0 是因为题目测试程序给的测试数据中有n = 0 时期望答案为1的设定。
return 1;
}
if (n == 1 || n == 2)
return n;
int[] array = new int[n + 1];
array[1] = 1;
array[2] = 2;
for (int i = 3; i <= n; i++)
array[i] = array[i - 1] + array[i - 2];
return array[n];
}
}
这样就不会出现
栈溢出
的情况了,但是可以看到使用数组还是占用了一定的空间,不够简洁,于是再次改进。
public class Solution {
/**
* @param n: An integer
* @return: An integer
*/
public int climbStairs(int n) {
if (n == 0) {//这里判断n == 0 是因为题目测试程序给的测试数据中有n = 0 时期望答案为1的设定。
return 1;
}
if (n == 1 || n == 2)
return n;
int f1 = 1;
int f2 = 2;
int fn = 0;
for (int i = 3; i <= n; i++) {
fn = f1 + f2;
f1 = f2;
f2 = fn;
}
return fn;
}
}
此方法就是每次将
f1
和f2
向后移动一次,以记录数据。避免浪费资源. 如下:
1, 2, 3, 5, 8, 13 ......
f1, f2, fn,
1, 2, 3, 5, 8, 13 ......
f1, f2, fn
1, 2, 3, 5, 8, 13 ......
f1, f2, fn