方法：动态规划
①确定状态：dp[i] 为到达第 i 个台阶的方法总数
②转移方程：dp[i] = dp[i - 1] + dp[i - 2];
③初始条件和边界情况：dp[1]?=?1;? dp[2]?=?2;
④计算顺序：因为 dp[i] 由 dp[i-1] 和 dp[i-2]推出，所以从前往后遍历
class Solution {
public int climbStairs(int n) {
//第 n 个台阶只能从第 n - 2 或第 n - 1 个台阶爬上来，
//到第 n - 2个台阶的走法 ＋ 到第 n - 1 个台阶的走法 = 到第 n 个台阶的走法
if (n <= 2) return n;
//确定状态
int[] dp = new int[n + 1];
//初始条件
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
//状态转移方程以及计算顺序
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}--滚动数组实现
class Solution {
public int climbStairs(int n) {
int p = 0, q = 0, r = 1;
for (int i = 1; i <= n; ++i) {
p = q;
q = r;
r = p + q;
}
return r;
}
}
