代码随想录算法训练营打卡Day38 | LeetCode509 斐波那契数、LeetCode70 爬楼梯、LeetCode746 使用最小花费爬楼梯

摘要

通过简单的题目来熟悉方法论。
和贪心法只需要每一步保证局部最优相比，动态规划的下一步的决策需要根据之前的状态推导。贪心法只需要保存和局部最优相关的信息，动态规划需要保存之前状态的信息，需要保存的信息更多。

动态规划理论基础

什么是动态规划？

动态规划（英语：Dynamic programming，简称 DP），是一种把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。
用“状态”来描述通过子问题求解复杂问题的过程，下一步的状态需要由之前的状态推到出来。这一点和贪心有明显区别，贪心只需要根据局部最优来进行下一步，只需要保存和局部最优相关的信息；而动态规划需要根据之前的状态进行推导，需要保存的信息更多。

动态规划的解题步骤

确定dp数组以及数组下标的含义
确定状态转移方程或递推公式
分析初始状态，确定dp数组如何初始化
确定遍历方法，如循环的嵌套顺序，先遍历哪个下标
举例推导dp数组（辅助思考或辅助调试代码）

通过Debug来帮助理解动态规划

即上述的第 5 步，用具体的例子来推导 dp 数组，然后在实现代码中将 dp 数组的构造过程打印出来。

举例推导状态转移公式（递推公式）
打印 dp 数组的构造过程（更新日志）
实现代码打印出的 dp 数组和自己推导的是否一致

LeetCode509 斐波那契数

509. 斐波那契数 - 力扣（Leetcode）

确定dp数组及数组下标的含义：dp数组保存斐波那契数列，dp[i]为斐波那契数列中的第 i个数。
确定递推公式：题目已经给出递推公式，即

$dp[i] = \begin{cases} 0, & i=0 \\ 1, & i=1 \\ dp[i - 1] + dp[i - 2], & i \ge 2 \end{cases}$

初始状态也可以由递推公式得到，即dp[0]=0; dp[1]=1
dp数组是一维的，已知的初始状态是i=0和i=1，所以i从小到大遍历构造dp数组

不难得到如下题解代码

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

当然，注意到每一步其实只需要前两步的状态，可以降低空间复杂度到O(1)

class Solution {
public:
    int fib(int n) {
        if (n < 2) return n;
        int pre_2 = 0;
        int pre_1 = 1;
        int res = pre_2 + pre_1;
        for (int i = 2; i <= n; i++) {
            res = pre_2 + pre_1;
            pre_2 = pre_1;
            pre_1 = res;
        }
        return res;
    }
};

也可以通过递归形式实现

class Solution {
public:
    int fib(int n) {
        if (n < 2) return n;
        return fib(n - 1) + fib(n - 2);
    }
};

LeetCode70 爬楼梯

70. 爬楼梯 - 力扣（Leetcode）

确定dp数组及数组下标的含义：dp[i]的含义是，从第1级楼梯到第i级楼梯有多少种方法。
确定递推方程：先看简单的子问题：
1. 一级楼梯都没有，一开始就在楼顶，那就是1种方法
2. 只有一级楼梯，那就是1种方法
3. 有两级及以上的楼梯时，到达第i级楼梯有两种方法，即从第i - 1级楼梯走一级到第i级楼梯，或从第i - 2级楼梯走两级到第i级楼梯。

$dp[i]= \begin{cases} 1, & i = 0 \\ 1, & i = 1 \\ dp[i - 1] + dp[i - 2], & i \ge 2 \end{cases}$

确定初始状态，从i=0开始走楼梯，根据递推方程dp[0]=0; dp[1]=1。
确定遍历方法，dp数组只有一维，走楼梯从i=0开始走，i逐渐增大

题解代码如下

class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp(n + 1);
        dp[0] = 1;
        if (dp.size() > 1) dp[1] = 1;
        for (int i = 2; i < dp.size(); i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};

LeetCode746 使用最小花费爬楼梯

746. 使用最小花费爬楼梯 - 力扣（Leetcode）

确定dp数组及数组下标的含义：dp[i]的含义是到达第i级台阶的最小花费。
确定递归方程，先从简单的子问题开始
1. 只有一级台阶，那就只能从这级台阶开始，支付对应的费用，爬到楼顶
2. 只有两级台阶，爬到楼顶就有两种可能：一是从下标为0的台阶开始向上爬两个台阶到楼顶，二是从下标为1的台阶开始向上爬一个台阶到楼顶。此时的最小花费应该是这两级台阶中的最小值。
3. 再来看第i级台阶，到达第i级台阶就有两种可能：一是从下标为i-2的台阶开始向上爬两级台阶到第i级台阶；二是从下标为i-1的台阶开始向上爬一级台阶到第i级台阶。假设前面到达i-1或i-2级台阶时都是最小花费，则到达第i级台阶的最小花费是在dp[i-1]+cost[i-1]和dp[i-2]+cost[i-1]中取最小值。
- 设有n级台阶（下标从0开始），注意到从第0级台阶或第1级台阶开始是，没有额外花费的。
$dp[i]= \begin{cases} 0, & i \le 1 \\ min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]), & i \ge 2 \end{cases}$
分析初始状态，确定dp数组如何初始化，由上面的递推方程可以得到dp数组如何初始化
确定遍历方法，从低级台阶爬到高级台阶，i逐渐递增