[leetcode hot 150]第七十题，爬楼梯（动态规划）

题目：

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

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

爬到第 n 阶楼梯的方法数量等于爬到第 n-1 阶和第 n-2 阶的方法数量之和,即: 

f(n) = f(n-1) + f(n-2)

边界条件

还需要考虑边界条件:

• 如果 n=1,那么只有 1 种方法,即爬 1 阶
• 如果 n=2,那么有 2 种方法,即爬 1 阶再爬 1 阶,或者直接爬 2 阶

所以可以初始化:

f(1) = 1

f(2) = 2

public class no_70 {
    public static void main(String[] args) {
        int n = 3;
        System.out.println(climbStairs(n));
    }

    public static int climbStairs(int 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];

    }
}