LeetCode070（爬楼梯）

发表于 | 分类于 ，

题目：

　　假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。

思路：

　　设n阶台阶有f(n)种不同的方法爬到楼顶，爬1个台阶后有f(n-1)种不同方法爬到楼顶，爬2个台阶后有f(n-2)种不同的方法爬到楼顶，则f(n)=f(n-1)+f(n-2),
即得出了递推式，同时也是斐波那契数列的递推式，可以使用递归实现，但可能超出限制时间。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// DP
public int climbStairs1(int n) {
	int[] count = new int[n];
	if (n == 1) {
		return 1;
	}
	if (n == 2) {
		return 2;
	}
	count[0] = 1;
	count[1] = 2;
	for(int i = 2;i < n;i++) {
		count[i] = count[i-1]+count[i-2];
	}
	return count[n-1];
}
	// 递归
public int climbStairs2(int n) {
	if (n == 1) {
		return 1;
	}
	if (n == 2) {
		return 2;
	}
	return climbStairs2(n-1) + climbStairs2(n-2);
}

复杂度分析：

动态规划：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(n)。

递归：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(n)。

原题链接：

https://leetcode-cn.com/problems/climbing-stairs/