81. 爬楼梯（动态规划/70）

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
假设：1 <= n <= 45。
示例：输入：n = 3；输出：3。(1,1,1; 1,2; 2,1)

【分析】
到达第n阶的方法数等于达到第n-1阶和到达第n-2阶的方法数之和。
要到达第 n 阶，你可以选择从第 n−1 阶走一步上来，或者从第 n−2 阶走两步上来（从n-2阶走一步再走一步的情况，走一步时和第一种方法重了）。因此，到达第 n 阶的总方法数是到达第 n−1 阶和第 n−2 阶的方法数之和。
这种方法确保了每个子问题只被解决一次，并且其解被存储起来供后续使用，从而提高了算法的效率。
res[n]=res[n-1]+res[n-2]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution{
	public int ClimbStairs(int n){
		if(n<=2){
			return n;
		}
		
		//这两个变量的值随着n的变大动态地变大
		int resN_2=1;//初始化可指代n=1时的result
		int resN_1=2;//初始化可指代n=2时的result
		int result=0;
		for(int i=3;i<=n;i++){
			result=resN_1+resN_2;//当下的i的result是由n-1时的result和n-2时的result组成
			resN_2=resN_1;//res[n-1]对于下一轮就是res[n-2]
			resN_1=result;//当前res对于下一轮就是res[n-1]
		}
		return result;
	}
}