爬楼梯

题意

假设你正在爬楼梯,需要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+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=2n=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;
    }
}

此方法就是每次将 f1f2 向后移动一次,以记录数据。避免浪费资源. 如下:

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

原题地址:

LintCode:爬楼梯

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 快乐数

    一份执着✘
  • 删除排序数组中的重复数字Ⅱ

    一份执着✘
  • 落单的数

    一份执着✘
  • 数学--数论--HDU1222 狼和兔子(最大公约数)

    兔子必须藏在其中一个洞中。狼以逆时针方向搜索兔子。他第一个进入的洞是一个用0签名的洞。然后,他将每m个洞进入一个洞。例如,m = 2和n = 6,狼将进入带有符...

    风骨散人Chiam
  • Leetcode 365. Water and Jug Problem

    You are given two jugs with capacities x and y litres. There is an infinite amou...

    xindoo
  • 聊聊flink的AbstractNonHaServices

    flink-runtime_2.11-1.7.1-sources.jar!/org/apache/flink/runtime/highavailability/...

    codecraft
  • 2020-09-12:手撕代码:最小公倍数,复杂度多少?

    1.【更相减损法】=【等值算法】,避免了取模运算,但是算法性能不稳定,最坏时间复杂度为O(max(a, b)))。

    福大大架构师每日一题
  • golang之递归

    超蛋lhy
  • LeetCode 914. 卡牌分组(最大公约数)

    每组都有 X 张牌。 组内所有的牌上都写着相同的整数。 仅当你可选的 X >= 2 时返回 true。

    Michael阿明
  • 如何比较?Comparable还是Comparator

    我家开了个小卖店,为了实现数字化管理,我准备写个后台程序来对所有货物进行管理。首先定义了这个实体类,这个类就是“货物”类,num指的是他的编号,s指他的名称或描...

    naget

扫码关注云+社区

领取腾讯云代金券