Leetcode 70.爬楼梯

题目要求

  • 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

  • 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。

  1. 1 阶 + 1 阶
  2. 2 阶

示例 2:
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。

  1. 1 阶 + 1 阶 + 1 阶
  2. 1 阶 + 2 阶
  3. 2 阶 + 1 阶

动态规划

动规五部曲

  1. 确定dp数组（dp table）以及下标的含义
    dp[i] 表示第n阶楼梯的爬法数

  2. 确定递推公式
    因为到达第n层的方法只有两种：

  • 从第n-1层爬1阶到达
  • 从第n-2层爬2阶到达
    所以递推公式为：dp[i] = dp[i - 1] + dp[i - 2]

  1. dp数组如何初始化
    因为要求第 n 阶楼梯的爬法数，所以需要一个长度为 n + 1 的数组来存储从 0 到 n 的爬法数。
    int[] dp = new int[n + 1];
    dp[0] = 1, dp[1] = 1
    实际上dp[0] = 1 是为了方便计算，因为爬到第0层只有一种方法，即不爬。

  2. 确定遍历顺序
    从前往后遍历，因为后面的值需要由前面的值相加得到

  3. 举例推导dp数组
    前10个数：

i 0 1 2 3 4 5 6 7 8 9
dp[i] 1 1 2 3 5 8 13 21 34 55 
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int climbStairs(int n) {
        if (n == 1) return n;
        int[] dp = new int[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];
    }
}