理论基础

动态规划五部曲

1. 确定dp数组
2. 递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 打印dp数组

509. 斐波那契数

本题比较简单，直接套用动态规划五部曲即可

class Solution {
    public int fib(int n) {
        if (n <= 1) return n;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i < n + 1; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

70. 爬楼梯

70. 爬楼梯 - 力扣（LeetCode）
本题主要能看出走n阶方法=n-1阶的方法+n-2阶的方法（因为前提是只能走1或2步），那么本质就是斐波那契数

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 + 1; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

746. 使用最小花费爬楼梯

746. 使用最小花费爬楼梯 - 力扣（LeetCode）
本题要明白一个前提，楼顶并不是数组最后一个元素，而是在其下一位，也就是超出数组范围，所以dp数组大小应该是是length+1，而dp数组的含义就是到达i层需要的最小花费

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int[] dp = new int[cost.length + 1];
        dp[0] = 0;
        dp[1] = 0;
        for (int i = 2; i < dp.length; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[cost.length];
    }
}