代码随想录动态规划——爬楼梯

题目

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

思路

动规五部曲：
记录一个一维数组来记录不同楼层的状态

1. 确定dp数组以及下标的含义
   dp[i]表示爬到第i层楼梯，有dp[i]种方法
2. 确定递推公式
   从dp[i]的定义可以看出，dp[i] 可以有两个方向推出来，因为一次最多走两个阶梯
   首先是dp[i-1]，上i-1层楼梯有dp[i - 1]种方法，再一步跳一个台阶到达dp[i]
   然后是dp[i - 2]，上i-2层楼梯有dp[i - 2]种方法，再一步跳两个台阶到达dp[i]
   所以dp[i] = dp[i - 1] + dp[i - 2]
3. dp数组如何初始化
   本题其实不用考虑dp[0]的情况，因为n为正整数，只用初始化dp[1] = 1，dp[2] = 2，然后从i = 3开始递推（但是力扣上过不了，答案要求必须要从dp[0]=1开始）
4. 确定遍历顺序
   从递推公式dp[i] = dp[i - 1] + dp[i - 2]中可以看出，遍历顺序一定是从前向后遍历的
5. 举例推导dp数组
   比如n=5的时候，dp数组应该是1，2，3，5，8，如果代码出问题就把dp数组打印出来，看看和推导的错在哪里

java代码如下：

class Solution {
	public int climbStairs(int n) {
		int[] dp = new int[n+1];//这里初始化为n+1，取决于你定义的大小，本题是dp[0]一直到dp[n]，所以大小是n+1
		dp[0] = 1;
		dp[1] = 1;
		for(int i = 2;i <= n; i++){
			dp[i] = dp[i-1] + dp[i-2];
		}
		return dp[n];
	}
}
1
2
3
4
5
6
7
8
9
10
11