【算法】一文带你从浅至深入门dp动态规划-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法】一文带你从浅至深入门dp动态规划。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、前言

本文要为大家带来的是dp动态规划，相信这是令很多同学头疼的一个东西，也是在大厂面试中很喜欢考的一个经典算法

🔰 本文总共会通过四道题来逐步从浅至深地带读者逐步认识dp动态规划

二、动态规划理论基础

首先在讲解题目之前，我们要先来说说动态规划理论基础，让大家知道到底什么是【动态规划】

1、基本概念

动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。

如果读者有学习过【贪心算法】的话，就可以知道其和动态规划是很类似的，但是呢却有着本质的区别，对于贪心而言，是局部直接选最优，但是对于动规而言则是通过上一个状态去推导出下一个状态

例如：有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大

本题若是使用动态规划来做，需要先表示出数组dp的状态，通过dp[j-weight[i]]推导出dp[j]，然后得出 状态转移方程max(dp[j], dp[j - weight[i]] + value[i])，才能计算出最终的结果
但若是使用贪心算法来求解的话，直接在每次拿物品选一个最大的或者最小的就完事了

💬 所以大家在做题的时候只要牢牢记住它们而言的最本质区别即可，题目刷多了，自然也就很好区分

2、动态规划五部曲【✔】

清楚了动态规划的基本概念后，我们再来看看在解决动态规划的问题时的解题步骤👇

做动规题目的时候，很多同学会陷入一个误区，就是以为把 状态转移公式 背下来，照葫芦画瓢改改，就开始写代码，甚至把题目AC之后，都不太清楚dp[i]表示的是什么
所以遇到一些同种类的其他题目时，就会手足无措，状态转移公式（递推公式）是很重要，但动规不仅仅只有递推公式。对于动态规划问题，我将拆解为如下五步曲：
1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式（状态转移方程）
3. dp数组如何初始化
4. 确定遍历顺序，对dp数组进行填表
5. 确认返回值 / 输出内容

一些同学可能想为什么要先确定递推公式，然后再考虑初始化呢？

因为一些情况是递推公式决定了dp数组要如何初始化！

所以我们要先根据dp的状态，来推导出状态转移方程，接着再通过去分析这个方程，然后推敲出dp数组要怎样去做一个初始化才比较合适，不会导致越界的问题。所以对于那些只知道记公式但是不知道如何初始化和遍历数组的同学，就会显得尴尬

3、出错了如何排查？

相信大家在写代码的时候一定会出现各种各样的Bug，那要如何去解决呢，还记得之前的 LeetCode转VS调试技巧吗？

但是对于动态规划而言，就是在力扣中 把dp数组打印出来，看看究竟是不是按照自己思路推导的！。这是最简洁明了的方式，所以我们遇到问题后不要害怕，而是要逐步地去分析、排查问题，加强自己排查错误的能力，如果还是不会了再去请教别人，但是在请教之前也先请问问自己下面的三个问题：
1. 这道题目我举例推导状态转移公式了么？
2. 我打印dp数组的日志了么？
3. 打印出来了dp数组和我想的一样么？
把上面三个问题想明白之后再去问别人，即经过了自己的思考之后，有了自己的见解，这样才能更有效果，并且做到事半而功倍

三、实战演练🗡

在了解了一些动态规划的基础理论之后，我们还是要进入实际的问题

0x00 斐波那契数

原题传送门：力扣509.斐波那契数

首先第一道动态规划的入门题必须选择的就是【斐波那契数】，下面我会给出三种解法

首先是最简单的一种，即 递归解法，不做详细展开，不懂可以看看 C语言函数章节中的函数递归，就会很清楚了

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

接下去的话就是我们本题的重点即 动态规划 的解法

首先的话就是要去创建dp数组，这里使用到的是 C++STL之vector类，如果有不懂的同学可以去看看，我们初始化出一个大小为n + 1的数组

vector<int> dp(n + 1);

接下去我们要去做的就是要去推导出这个 状态表示方程，那对于斐波那契数列我们很熟悉，后一个数等于前两个数之和，而且后面的数依赖于前面的数，所以我们的遍历数组也应该是从左向右

dp[i] = dp[i - 2] + dp[i - 1];

再者我们就需要通过上面这个 状态表示方程 来对这个dp数组去做一个初始化的工作，此时我们需要去考虑的就是这个越界的问题，因为当前的dp[i]依赖的是前两个数，所以若此刻的i == 0的话，前两个数就会发生越界的情况；若是i == 1，第一个数就会发生越界，所以我们要对前两个数做一个初始化的操作

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划

dp[0] = 0, dp[1] = 1;

那在初始化完成之后，我们就可以去做遍历填表的工作了，因为前两个数字已经被初始化了，所以从下标为2的地方开始向后遍历

for(int i = 2; i <= n; ++i)
{
    dp[i] = dp[i - 2] + dp[i - 1];
}

当遍历填表结束后，因为所求的是第N个斐波那契数，所以我们就需要去返回dp[n]

return dp[n];

以下即为整体代码展示

class Solution {
public:
    int fib(int n) {
        if(n <= 1)  return n;

        // 1.创建dp表
        vector<int> dp(n + 1);

        // 2.初始化
        dp[0] = 0, dp[1] = 1;

        // 3.遍历填表
        for(int i = 2; i <= n; ++i)
        {
            dp[i] = dp[i - 2] + dp[i - 1];
        }

        // 4.返回值
        return dp[n];
    }
};

读者可以通过执行结果来看看dp动态规划解法的优势

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划

再下面一种方法则是通过 滚动数组 的形式进行求解

可能读者有所不太理解什么是【滚动数组】，如果你了解迭代算法的话就可以知道，其实并不复杂。原理也是一样的，我们直接通过定义一维数组

int dp[2];

然后将上面dp动态规划中的 递推公式 转换成迭代的形式即可

for(int i = 2; i <= n; ++i)
{
    sum = dp[0] + dp[1];
    // 迭代
    dp[0] = dp[1];
    dp[1] = sum;
}

其余的没有大变化，代码如下：

class Solution {
public:
    int fib(int n) {
        if(n <= 1)  return n;
        int sum = 0;
        int dp[2];      // 一维数组模拟
        dp[0] = 0, dp[1] = 1;

        for(int i = 2; i <= n; ++i)
        {
            sum = dp[0] + dp[1];
            // 迭代
            dp[0] = dp[1];
            dp[1] = sum;
        }
        return dp[1];   // 最后累加的结果存入了dp[1]
    }
};

稍做了一些优化，看看运行效率

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划

0x01 第N个泰波那契数

原题传送门：力扣1137.第 N 个泰波那契数

看完斐波那契数之后，我们再来看一个东西叫做【泰波那契数】，不知读者有否听说过呢？

1、题目解读

首先我们来解读一下本题的意思🔍

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划

相信读者在看到【泰波那契数】的时候，不禁会联想到【斐波那契数】，它们呢是一对孪生兄弟，这个 泰波那契数 相当于是 斐波那契数 的加强版
我们首先可以来看到这个递推公式Tn+3 = Tn + Tn+1 + Tn+2，读者可能看不太懂，我们将其做一个转换为Tn = Tn-1 + Tn-2 + Tn-3，即把所有n都统一-3。那么第N个泰波那契数就等于前面3个泰波那契数的和

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划

看到上面的T3，就是前3个数的和等于2，以此类推T4就是T1 + T2 + T3 = 4

2、解题方法

看完了上面对于题目的分析之后，下面我将介绍两种解法

① dp动态规划

首先的话就是本题需要掌握的重点即【动态规划】的解法，我们要分成五步去求解

状态表示

首先读者要清楚的是在求解动态规划的题目时，都是需要一个dp数组的，那么对于【状态表示】的含义就是dp表里的值所表示的含义

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划

那这个状态表示是怎么来的呢？

① 第一个呢就是按照题目要求来，即dp[i]表示的就是第i个泰波那契数列的值

② 第二个呢则是需要读者有丰富的刷题经验，可以读完题目之后就得出对应的结果

③ 第三个呢则是在分析问题的过程中，发现重复的子问题

如果读者之前有接触过类似的动态规划问题的话，就会看到一些题解里讲：这道题的 状态表示 是怎样的，然后就直接讲本题的 状态表示方程，根本没有说这道题的状态表示是怎么来的。这个得来的过程我会在其他动态规划的题目中进行讲解

👉 所以读者在解类似的问题时一定要知道下面的这个【状态表示方程】是怎么来的，做到 “ 知其然，知其所以然 ”

状态表示方程

那么本题的状态表示方程为dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

初始化

在清楚【状态表示方程】该如何写之后，我们要去做的就是对这个dp数组做一个初始化的工作。看到下面的这个dp数组，如果在一开始我们的下标取值就到0的话，那么i - 1、i - 2、i - 3这些就会造成越界

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划

因此我们要给这个dp数组去做一个初始化，具体的就是对前三个数据即dp[0]、dp[1]、dp[2]分别初始化为【0】【1】【1】，那我们在后面遍历计算的时候就只需要从下标为3的位置开始即可

 dp[0] = 0, dp[1] = dp[2] = 1;

填表顺序

接下去的话就是把dp数组按照 状态表示方程 给填充好即可

for(int i = 3; i <= n; ++i)
{
    // 状态转移方程
    dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
}

返回值

最后一块我们处理返回值，根据题目要求我们是要返回【第 n 个泰波那契数 Tn 的值】，所以直接 return dp[n] 即可

但是呢，若只考虑上面的这一些，在提交的时候是会出现越界的情况，因为在题目中给出的n的范围为[0, 37]，因此对于dp[0]还好说，但对于后面的数据就会出现越界的情况

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划

因此我们还需要去考虑一些边界的问题

// 边界问题处理
if(n == 0)  return 0;
if(n == 1 || n == 2)    return 1;

👉 整体代码会在最后给出

② 迭代优化✔

看完上面这一种，我们再来看看其是否可以去做一个优化

如果读者有接触过迭代算法的话，应该很快能想到本题的思路，因为是三个三个去做的累加，所以我们在这里可以定义三个变量a、b、c，它们累加后的值可以放到变量d中

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划

因此在累加完一轮之后，我们就需要去做一个迭代的操作

a = b; b = c; c = d;

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划

那么在最后我们所需要返回的值就是这个d

return d;

3、复杂度

时间复杂度:

对于第一种dp的解法，其时间复杂度为 $O (n)$ ，而对于第二种迭代的解法时间复杂度为 $O (1)$

空间复杂度:

对于第一种dp的解法，其空间复杂度为 $O (n)$ ，而对于第二种迭代的解法时间复杂度为 $O (1)$

👉 所以就这么对比下来迭代优化的方法还是值得大家去掌握的

4、Code

首先是第一种dp动态规划的解法

class Solution {
public:
    int tribonacci(int n) {
        // 边界问题处理
        if(n == 0)  return 0;
        if(n == 1 || n == 2)    return 1;
        // 1.创建dp表
        vector<int> dp(n + 1);

        // 2.初始化
        dp[0] = 0, dp[1] = 1, dp[2] = 1;

        // 3.填表
        for(int i = 3; i <= n; ++i)
        {
            // 状态转移方程
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }

        // 4.返回值
        return dp[n];
    }
};

然后的话是第二种利用迭代优化的方法

class Solution {
public:
    // 空间优化
    int tribonacci(int n) {
        // 特殊情况处理
        if(n == 0)  return 0;
        if(n == 1 || n == 2)    return 1;
        int a = 0, b = 1, c = 1, d = 0;
        for(int i = 3; i <= n; ++i)
        {
            d = a + b + c;
            // 迭代
            a = b; b = c; c = d;
        }
        return d;
    }
};

0x02 爬楼梯

原题传送门：力扣70.爬楼梯

我们再来看一道和斐波那契数很像的题目，看了代码后你就会有这样的感觉

题目意思很简单，若是你现在在爬楼梯的话，每次只能上1 / 2个台阶，请问上到第N个台阶有多少种不同的方法。这个其实也和【青蛙跳台阶】非常得类似，不过在那个时候我们是使用递归来进行求解的，这里我们要考虑使用dp动态规划

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划

不必多解释，直接上代码，这里唯一要注意的一点就是在初始化的时候是要去初始化dp[1]和dp[2]，而不是去初始化dp[0]，因为台阶并没有0号台阶，而是从1号开始

class Solution {
public:
    int climbStairs(int n) {
        if(n <= 2)  return n;
        vector<int> dp(n + 1);
        dp[1] = 1;  // 从第一层楼梯开始初始化
        dp[2] = 2;

        for(int i = 3; i <= n; ++i)
        {
            dp[i] = dp[i - 2] + dp[i - 1];
        }
        return dp[n];
    }
};

0x03 三步问题

原题传送门：面试题0801.三步问题

看完了爬楼梯之后，我们再来做一个进阶，解决一个三步问题

首先来看一下题目所描述的意思，刚才我们一次是只能上1阶、2阶，现在的话是可以上3阶了，那么爬楼梯的种类就会增多

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划

那我们先来分析一下，到[1]号台阶有1种方法，到[2]号台阶有2种方法，分别是1 1和0 2，到[3]号台阶则是有1 1 1、0 2 1、0 1 2、0 3，可以看做是【1 + 1 + 2 = 4】，那么以此类推到达第4号台阶即为【1 + 2 + 4 = 7】

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划

那分析完题目后我们就要根据动规五部曲来完成对题目的分析

首先第一步就是需要去确定状态表示，那经过我们的分析，本题的dp[i]表示的就是到达 i 位置时，一共有多少种方法

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划

接下去呢我们就需要通过这个i位置的状态以及dp数组的含义，去进一步划分思考问题。那根据题目中来看，因为是需要走三步，我们从i位置往前推出i - 3、i - 2、i - 1这三个位置

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划

那么从这三个位置到下标为i的位置即为dp[i - 1]、dp[i - 2]、dp[i - 3]
很明显我们就可以推出状态转移方程为：

dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划

接下去呢我们就需要去考虑初始化的问题了，主要是要考虑到越界这一块的问题，这个我在讲解前面的题目时也有讲到过，因为不存在0号台阶，所以当此时的 i == 1 的话，前面的三个数就会发生越界的问题

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划

那我们就可以对这三个位置去做一个初始化的工作了

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划

接下去我们要来确立的就是填表顺序了，上面说到过这个i位置的值依赖于前3个值，所以我们的填表顺序就需要【从左往右】来进行

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划

那么最后的返回值即为dp[n]

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划

根据上面的五部曲，我们先来看看代码该如何去进行书写

class Solution {
public:
    int waysToStep(int n) {
        // 1.创建dp表
        vector<int> dp(n + 1);

        // 2.初始化
        dp[1] = 1, dp[2] = 2, dp[3] = 4;

        // 3.填表
        for(int i = 4; i <= n; ++i)
        {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }

        // 4.返回值
        return dp[n];
    }
};

首先第一个问题就是很明显的越界问题，反应快的同学应该很快就可以察觉到时前面三个位置的问题

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划

所以我们应该在最前面加上这样的一些判断

// 考虑越界问题
if(n == 1 || n == 2) return n;
if(n == 3)  return 4;

但是呢，在提交之后发现还有错误存在：仔细观察的话发现这是一个 运行时异常，叫做signed integer overflow —— 有符号数的整数溢出

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划

原题：结果可能很大，你需要对结果模1000000007

如果读者对题目本身还有印象的话就可以知道本题的结果可能会很大，所以题目中讲到要我们去做【取模】的运算

这里我们先去定义一个常量，因为对于1000000007它的值的即为1e9 + 7

// 定义常量
const int MOD = 1e9 + 7;

然后在填表遍历的时候就可以去对所计算出来的值做一个取余的操作

dp[i] = ((dp[i - 1] + dp[i - 2]) % MOD + dp[i - 3]) % MOD;

以下即为整体的代码展示：

class Solution {
public:
    int waysToStep(int n) {
        // 定义常量
        const int MOD = 1e9 + 7;

        // 考虑越界问题
        if(n == 1 || n == 2) return n;
        if(n == 3)  return 4;
        // 1.创建dp表
        vector<int> dp(n + 1);

        // 2.初始化
        dp[1] = 1, dp[2] = 2, dp[3] = 4;

        // 3.填表
        for(int i = 4; i <= n; ++i)
        {
            dp[i] = ((dp[i - 1] + dp[i - 2]) % MOD + dp[i - 3]) % MOD;
        }

        // 4.返回值
        return dp[n];
    }
};

然后就看到很顺利地通过了

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划

0x04 使用最小花费爬楼梯⭐

原题传送门：746.使用最小花费爬楼梯

知道了怎么去爬楼梯之后，我们再来做一个进阶：如何利用最小的花费去爬楼梯，本题很锻炼大家的dp思维，准备好，发车了🚗

首先我们来分析一下题目的意思，就是我们在向上爬楼梯的时候，需要去支付一定的费用；可以选择从 下标为 0 或下标为 1 的台阶开始爬楼梯，题目要我们计算的就是怎样去爬才可以使得爬到楼顶所需要花费的最少
在这里读者尤其要注意的一个点是关注楼顶在哪里，仔细看示例就可以发现楼顶应该是在cost[n]的位置才对

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划

解法一

接下去我们就可以开始通过一步一步地去进行求解

首先还是一样，我们要去定义dp数组并且了解这个dp[i]所表示的含义是什么，即到达i位置时的最小花费

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划

接下去呢，我们就要通过当前的这个i的位置之前或者之后的状态去推导出【状态转移方程】，来表示dp[i]

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划

因为我们可以选择向上爬一个或者两个台阶，所以就将求解dp[i]转换为了两个子问题：
1. 先到达 i - 1 位置，然后支付 cost[i - 1]，走一步
2. 先到达 i - 2 位置，然后支付 cost[i - 2]，走二步
可以看到，因为我们在到达一个台阶时，需要支付完一笔费用后才能前行，那么前者可以转换为dp数组 —— 到达 i 位置的最小花费来表示；后者的话则可以转换为cost数组 —— 从每个台阶上爬需要支付的费用

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划

虽然是分成了两个子问题来进行求解，但是呢题目给我们的要求是最小花费，所以我们应该要取的是二者之中的较小值。那么【状态转移方程】即为

dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);

那么当这个【状态转移方程】写出来后我们就要去考虑这个 初始化 的问题了，因为上 0号 和 1号 台阶的时候我们是不需要支付任何费用的，并且为了防止不越界，我们在初始化的时候应该令dp[0] = dp[1] = 0

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划

接下来的话就要去考虑我们的填表顺序了，因为dp[i]是依赖于dp[i - 1]和dp[i - 2]，所以我们需要先算出前面的2个数才能去得到这个dp[i]，因此这个填表的顺序应该是 从左向右

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划

最后的话就是我们的返回值dp[n]了

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划
以下就是代码了

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        if(n <= 1)  return n;
        // 1.定义dp数组
        vector<int> dp(n + 1);
        // 2.初始化
        dp[0] = dp[1] = 0;
        // 3.填充dp数组
        for(int i = 2; i <= n; ++i)
        {
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        // 4.返回结果
        return dp[n];
    }
};

以下是提交后的结果

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划

解法二

看完解法一之后，我们再来看看解法二

首先的话还是一样，我们要去确定这个 状态表示，在解法二中，dp[i]表示的 从i位置出发，到达楼顶时的最小花费
那么接下去就慢慢地推导这个【状态转移方程】，再来回顾一下解法一dp[i]表示为到达i位置时的最小花费

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划

那此时我们从i位置出发也可以分为两种
1. 支付当前台阶所需费用，并向后走一步，从i + 1位置到终点
2. 支付当前台阶所需费用，并向后走二步，从i + 2位置到终点
将上面的两个分析式转换为公式的话为
- cost[i] + dp[i + 1]
- cost[i] + dp[i + 2]

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划

那么最后的这个【状态转移方程】即为

dp[i] = min(cost[i] + dp[i + 1], cost[i] + dp[i + 2]);

接下去我们需要考虑的就是这个初始化的问题，首先读者要清楚的是我们在开这个dp数组的时候大小应该是多大呢？是n呢，还是n + 1呢？

立即揭晓答案：应该是[n]，为什么？原因就在于我们到达n级台阶的时候是不需要支付任何费用的，即dp[n] = 0，所以去开出这个空间也是浪费的，所以这一块地方应该是作为 楼梯顶部 才对
那么从dp[n - 1]到这个顶部的位置所需要支付的费用即为cost[n - 1]，那么从这个dp[n - 2]到这个顶部的位置所需要支付的费用即为cost[n - 2]

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划

接下去我们所需要考虑的就是 填表顺序，通过【状态转移方程】很明显可以看出我们需要先获取到dp[i + 1]、dp[i + 2]的值，才可以去推导出dp[i]的值，所以我们的填表顺序应该是从右往左的才对

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划

那最后需要考虑的就是返回值了，在本解法中，我们的dp数组表示的是 从第i个位置出发到达楼顶的最小花费
因为我们可以选择从第[0]或第[1]个位置出发，所有最后的结果就是取这两个位置所需花费的最小值

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划
以下是代码：

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        // 1.定义dp数组
        vector<int> dp(n);
        // 2.初始化【防止越界】
        dp[n - 1] = cost[n - 1], dp[n - 2] = cost[n - 2];
        // 从后往前遍历
        for(int i = n - 3; i >= 0; --i)
        {
            dp[i] = min(dp[i + 1] + cost[i], dp[i + 2] + cost[i]);
        }
        return min(dp[0], dp[1]);
    }
};

来看看优化后的效率

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划

0x05 解码方法*

力扣91. 解码方法

最后再来一道压轴题，本题是力扣里中等难度的题目。AC本题，可以让你对dp的理解进一步提升

首先的话我们来分析一下题目所表示的含义：在题目中会给到一个只包含数字的非空字符串s，然后要我们去对这个字符串做解码的操作，规则如下
- 'A' -> "1"
- 'B' -> "2"
- 'C' -> "3"
- 'Z' -> "26"
根据上面的解码规则我们进一步来看题目要求，因为这个字符串中所包含的不仅仅只有一个数字，所以在解码的时候便需要涉及到多种的可能性，最后所需要我们返回的也是解码方法的总数

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划

了解了题目的基本规则后，我们通过分析示例来进一步理解题目

首先看到示例1，s = “12”，那我们的解码方式就有两种，一种是“A B”（1，2），一种则是L（12）
然后看到示例2，s = “226”，那我们的解码方式就有三种，一种是“B B F”（2，2，6），第二种是V F（22,6），第三种呢则是B Z（2，26）
然后看到示例3，s = “06”，对于这个而言其实是存在问题的，因为“06”是无法映射到【F】的，只有“6”才可以映射到【F】，所以对于这种并不存在解码的方式

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划

好，当我们分析完题目中所给到的示例后，就需要通过dp动态规划来解决本题，接下去就是算法原理的讲解

首先第一步，还一样定义出一个dp数组，然后将其状态表示出来，这里的dp[i]则表示 以 i 位置为结尾时的解码方法总数

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划

然后接下去我们就要根据这个状态来推导出状态转移方程。我们通过这个dp数组来进行观察分析，此处我们考虑到两种情况，一个是就对i这个位置去做一个解码，第二种呢则是i - 1和i这两个位置去结合，结合完之后再去做解码的操作

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划

那这个时候有同学就会有疑问了，为什么不考虑i + 1这个位置呢？这个的话你就要反上去继续看我们所讲到的这个状态表示了。因为我们考虑的是 以 i 位置为结尾时的解码种数，对于后面的情况此时还没有考虑到，所以呢我们不需要去理会i + 1这个位置

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划

此时我们在求解dp数组的时候就就分为以下两种情况下：
1. s[i]去单独解码，分为两种情况，那对于单独的一个数其取值就有1 ~ 9的可能性，如果这个数为0的话则表示解码失败
2. s[i - 1]与s[i]合并去解码的话，我们就需要去考虑两个数了，第一个数要比10来得大，否则的话就要出现我们上面所讲到的06这种情况，第二个数的话要比26来的小，若二者都满足这种情况的话，则可以解码成功；否则的话就表示解码失败

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划

那我们对i这个位置单独去做解码的话，其实就相当于把[0, i - 1]解码的所有的方案数后面统一加一个字符就可以了，具体如下图所示👇
那我们要去找以i - 1为结尾的解码总数就可以表示为dp[i - 1]

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划

接下去我们再来考虑第二种情况，即我们要考虑到的是两位数合并后的情况，那所需要求解的便是[0, i - 2]这段区间中的解码总数，即dp[i - 2]

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划
以下即为我们分析所得出的【状态转移方程】

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划

接下去我们就来考虑初始化的问题

首先要初始化的位置相信读者在看了这么多道题之后应该很快就能反应过来了，我们在初始化的时候应该去初始化dp[0]和dp[1]这两个位置的值，对于dp[0]来说，我们是对单个位置上的数去做一个解码，那出现的情况也就只有【0】和【1】两种，数据的范围要在0 ~ 9之间
那对于dp[1]来说，我们要对合并的两数去做一个解码，那此时就会存在3种情况
- [0]即为这二者都不存在的时候
- [1]即为这二者中只有一者存在的情况
- [2]即为二者都存在的情况

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划

接下去我们再来看填表顺序

这一块很好理解，通过我们的【状态转移方程】可以看出后面的数依赖于前面的数，那么遍历的顺序即为从左往右

dp[i] = dp[i - 1] + dp[i - 2]

最后的话是关于返回值这一块，因为我们要找的是到第 i 个位置的解码总数，不过题目给出的是一个字符串，对于字符串的最后一个位置是n - 1，那么我们最后返回的结果dp[i - 1]

💬 由于本题代码比较得复杂，所以接下去分步骤讲解一下

首先我们要做的就是创建出dp表

// 创建dp表
int n = s.size();
vector<int> dp(n);

接下来要做的就是初始化工作，首先要去做的是初始化dp[0]，还记得我们上面分析的吗，当这个编码的范围在1 ~ 9之间的时候，所以在这里我们可以采取一个逻辑判断，让dp[0]只接收当前s[0]这个字符的值不为0的情况

// 初始化dp[0]
dp[0] = (s[0] != '0');

接下去呢我们考虑初始化dp[1]，首先考虑到两数单独编码的情况，若均不为0的话则表示可以进行解码

// 1.两数单独编码
if(s[0] != '0' && s[1] != '0')
	dp[1] += 1;

接下去的话我们还需考虑两数结合的情况，因为这边给到的是字符串，所以我们在取的时候需要将其- ‘0’转换为数字才可以，接下去根据我们刚才所分析的，去判断这个数是否在符合的范围内，若是的话才表示可以解码

// 2.两数结合
int t = (s[0] - '0') * 10 + s[1] - '0';     // 字符串转数字
if(t >= 10 && t <= 26)  
    dp[1] += 1;

其后我们才去考虑这个【填表】的事情，因为前两个位置dp[0]和dp[1]已经做了初始化，所以我们从第3个位置开始即可，然后你就可以发现这个填表的情况和我们在初始化时的场景非常类似，这里就不细说了

// 填表
for(int i = 2;i < n; ++i)   // 从第三个位置开始遍历
{
    // 单独编码的情况
    if(s[i] != '0') dp[i] += dp[i - 1]; 
    // 两数结合的情况
    int t = (s[i - 1] - '0') * 10 + s[i] - '0';
    if(t >= 10 && t <= 26)  dp[i] += dp[i - 2];
}

最后的话返回dp[n - 1]即可

return dp[n - 1];

以下是整体的代码展示：

class Solution {
public:
// 状态转移公式
// dp[i] = dp[i - 1] + dp[i - 2]
    int numDecodings(string s) {
        // 创建dp表
        int n = s.size();
        vector<int> dp(n);

        // 初始化dp[0]
        dp[0] = (s[0] != '0');
        // 处理边界情况
        if(n == 1)  return dp[0];
        
        // 初始化dp[1]
            // 1.两数单独编码
        if(s[0] != '0' && s[1] != '0')
                dp[1] += 1;
            // 2.两数结合
        int t = (s[0] - '0') * 10 + s[1] - '0';     // 字符串转数字
        if(t >= 10 && t <= 26)  
            dp[1] += 1;

        // 填表
        for(int i = 2;i < n; ++i)   // 从第三个位置开始遍历
        {
            // 单独编码的情况
            if(s[i] != '0') dp[i] += dp[i - 1]; 
            // 两数结合的情况
            int t = (s[i - 1] - '0') * 10 + s[i] - '0';
            if(t >= 10 && t <= 26)  dp[i] += dp[i - 2];
        }
        return dp[n - 1];
    }
};

以下是执行结果

【算法】一文带你从浅至深入门dp动态规划,# 动态规划,算法,动态规划

四、总结与提炼

最后来总结一下本文所学习的内容📖

在本文中，我们学习到了大厂面试中非常喜欢考察一种算法类型叫做【动态规划】，它也是令许多同学望而却步的绊脚石之一，希望在阅读本文只后可以让你对dp动态规划有了一个清晰的认识
首先我们对动态规划的基础理论有了一些认识，清楚了什么是 动态规划 以及 动态规划的五部曲
之后呢我们就展开对习题的讲解和分析，从最基础的【斐波那契数】开始，一直到较为复杂的【解码问题】，随着一步步地深入，不知读者是否对动态规划有了进一步的认识