爬楼梯
题意
假设你正在爬楼梯，需要n步你才能到达顶部。但每次你只能爬一步或者两步，你能有多少种不同的方法爬到楼顶部？
样例
- n=1 方法只有一种就是1
- n=2 1+1 或者 2 两种方法
- n=3 1+1+1 或者 1+2 或者 2+1 三种方法
- …..
思路
逆向思维，例如 n = 4 ，那么他走的最后一步就只能是 1步 或者 2步，
如果最后走的是1级台阶，那么之前走的就是3级台阶， 如果之前走的是2级台阶，那么之前走的就是2级台阶，
于是得到4阶台阶的走法就是3阶台阶的走法加上2阶台阶的走法。也就是3 + 2 = 5种。
如果还不明白的话 我这样看：
n=1:n=2:1+12n=3:1+1+11+22+1n=4:1+1+1+11+2+12+1+11+1+22+2
在原来的
n=3的基础上，所有方法都加1步，变成了1+1+1+11+2+12+1+1。 然后再在n=2的基础上，所有方法都加2步，变成了1+1+22+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原题地址：
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2017-07-062，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
