Leetcode_70_Climbing Stairs

时间:2022-06-17 12:17:32

本文是在学习中的总结,欢迎转载但请注明出处:http://blog.csdn.net/pistolove/article/details/41851705

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

思路:

(1)题意为有一个n阶的*,一次你只能上一个或两个台阶,求你有多少种上台阶的方法。这道题其实很简单,就看你能不能想到它和某一个挺有名数列之间的联系,其考察我们发现规律和对常见数学数列理解的能力。

(2)这里我们不妨列举,并从中发现规律:

当n=1时,ways=1

当n=2时,有[2]  [1,1]两种情况,ways=2

当n=3时,有[1,1,1]  [1,2]  [2,1]三种情况,ways=3

当n=4时,有[1,1,1,1]  [2,2]  [1,1,2]  [1,2,1]  [2,1,1]五种情况,ways=5

当n=5时,有[1,1,1,1,1]  [2,2,1]  [2,1,2]  [1,2,2]  [1,1,1,2] [1,1,2,1] [1,2,1,1]  [2,1,1,1]八种情况,ways=8

(3)这样我想你一眼就能看出规律了,当n>3时,n对应的情况数字为n-1和n-2之和。此时,规律正好和斐波那契数列出现的规律对应。

(4)斐波拉切数列是这样一个数列:1、1、2、3、5、8、13、21、……在数学上,其被以递归的方法定义:F0=0,F1=1,Fn=F(n-1)+F(n-2)(n>=2)

(5)这样,我们就能够用递归的方法求得结果了。其实,很多题目看似挺难的样子,可能一时半刻想不到好的解题思路,就像这道题一样,刚开始我也没啥头绪,后来我就尝试先列举一排数字看看结果,然后就发现这不正好和斐波拉切数列对应的么,知道斐波拉切数列,结果也就出来了。所以我建议大家遇到看似挺难的题时,要去分析题目,一步步去理解,可能答案在你分析的过程中就会浮现出来,不要放弃。

(6)注:斐波拉切数列的另一种常见表述为“生兔子问题”。之前遇到的好多校招笔试题中都会出现这个题目,所以找工作同学可以多关注一下这个数列。其算法实现用递归很容易实现。希望对你有所帮助。谢谢。

算法代码实现如下所示:

public int climbStairs(int num) {
	//该题目和斐波拉切数列、生兔子问题属于同一类问题
	// 如果定义为 int则num=46时会越界;如果定义为long则num=92时会越界
	if (num <= 0)
		return 0;
	int[] sum = new int[num+1];
	for (int i = 0; i <= num; i++) {
		if (i == 0)
			sum[i] = 1;
		if (i == 1)
			sum[i] = 1;
		if (i > 1) {
			sum[i] = sum[i - 1] + sum[i - 2];
		}
	}
	return sum[num];
}