力扣70. 爬楼梯

力扣70. 爬楼梯

爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

1，确定dp table定义及其下标含义
2，求出递推公式
3，初始化（最小子情况）
4，确定遍历顺序
5，列表

这道题是很经典的一个动态规划或递归的题目，很多动态规划的题目可以由这题演变出来
例.
找零钱（多少种找的方法）https://leetcode-cn.com/problems/coin-change-2/
组合总和 Ⅳ https://leetcode-cn.com/problems/combination-sum-iv/
这些题目有一个特点就是需要排列组合的知识
而动态规划的方法可以求出之前所有排列的最佳情况然后加上自己会多出来的情况就形成一个新的最佳子情况用来合成我们要求的值

1，
这类题还有一个特点是一唯数组是一个比较好解的方法
子情况推导出目标情况基本都是下标从0到n
dp[i]为爬到第i的最优解

2，
第n层阶梯可以由第n - 1层和第n - 2层阶梯经过一步爬上来
排列组合重复问题：
当然第n - 2可以连走两步就会重复了所有不会走多步
第n - 1和第n - 2的路径情况绝对不一样（到达的层数都不同）
那么第n - 1到n层的路径和第n - 2到n的路径也就不一样
排列组合结果全面问题：
如果走一步的话n只能由第n - 1或第n - 2的情况过来，dp[n - 1]是n - 1阶梯的所有情况了，dp[n - 2]是n - 2阶梯的所有情况了，所以会很全面。
dp[n] = dp[n - 1] + dp[n - 2]

3,
最小子情况
dp[0] = 1;
dp[1] = 1;

4,
子情况推导到目标情况n从左到右遍历

一维数组

class Solution {
    public int climbStairs(int 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];
    }
}

也可以写成

class Solution {
    public int climbStairs(int n) {
        int dp[] = new int[n + 1];
        int nums[] = new int[]{1, 2};
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= n; i++) {
            for(int num : nums) {
                if(i - num >= 0) dp[i] += dp[i - num];
            }
        }
        return dp[n];
    }
}

比较符合这类题目的通解形式