关于动态规划（DP）全面讲解

Khalil_Fong

2025-07-17 13:16:26

发布于：广东

32阅读

0回复

0点赞

关于动态规划的全面讲解

🐧PENGUIN的动态规划讲解前言——————————动态规划（Dynamic Programming）从它诞生以来就一直是一个C++中的核心算法但因其的难度性劝退了众多的码农动态规划不是以其的数学推算或是程序编写能力出众而是它就像是一种从思维演算到题目建模的一类编程算法.

这篇文章以动态规划出发向各位解释其DP的本质运用范围核心特点 and 解题方法&思路向各位提供超详细的动态规划解析.

1.基础动态规划

动态规划的核心特点便是将一个大问题拆解成多个小问题 这些问题在逐步解决的同时不断地记录下来 这样就提高了解题效率 这两种方法便是动态规划中的划分子问题和记忆化搜索.
动态规划可以解决的问题多是像这两类:

1) 子问题重叠:

在划分完子问题后 发现有一些问题在递归时会出现步骤 or 答案重复计算的问题这样做会使得时间和空间有一定浪费可能单个子问题发生不是大事但多个子问题发生此事可能会超时或超空间.

2) 最优子结构:

这类问题是以一个个子问题达到最优解 从而使全局都达到最优解简单来说就是让每一个局部问题都竭尽所能的达到最好 从而使全局都达到最好.

动态规划的核心

动态规划以子问题重叠 最优子结构 最优原理和无后效性闻名前两个已经说过了我们来讲一讲后面两个最优原理和无后效性的核心概念是由美国数学家 理查德·贝尔曼（Richard Bellman） 所提出的他在20世纪50年代系统地发展了动态规划这一数学优化方法，并首次明确提出了最优化原理（Principle of Optimality）以及无后效性（Markovian property）的概念.

无后效性指在某个阶段(例如 $dp_i$ 被确定已经有某个权值)被确定有着一个状态时其阶段的状态就不会在改变了也不会影响的后面的决策只与现在的决策有关也就是过去的事件不会影响未来只与目前有关联.

最优原理指在每一个子问题中都达到最优的效果从而使全局达到最好最优性原理是动态规划里最重要的一块基石.

附如何解决动态规划

解决动态规划这类的问题需要分多个步骤思想如下:

step 1:确定level and step(层级和步骤）

以题目为准我们把一个题目转换成多个子问题又将一个子问题转换成多个子子问题如俄罗斯套娃一般的细分下去每一个需要解决的问题就是一种层级对于每个DP问题来说我们第一步要干的就是将一个大问题拆成多个小问题在逐步解决每个局部问题 同时我们还需要找到一个变量 能够把所有的小问题都串联在一起 在刚刚的斐波那契数列中斐波那契数列的项数就是变量它连接了每一个子问题.

step 2:找到状态转移方程

在划分完子问题后我们要想一想一件事情就是如何将所有的子问题给串联起来 我们得到了很多子问题也得到了我们需要的变量接下来就是使用变量将子问题都串联到一起
我们需要使用一句代码完成这件事情那这时状态转移方程就派上用场了.
（我们可以提前列出一个公式以其为中心编写核心程序).

状态转移方程和子问题及变量都密不可分所以我们在编写状态转移方程时需要多用上变量改变子问题最好包括到所有的变量以便为后面的程序提供更多可能.

step 3:处理边界问题

在找到状态转移方程后我们的思路构建已经完成一大半了但一些边界问题我们还是需要处理一下比如说斐波那契数列中的初始化问题 $F(0) = 0$ 和 $F(1) = 1$ 这样的边界值处理虽然这是一件极小的事情但在这类地方犯错误就会引起蝴蝶效应 导致后面的值一错再错 so这样的问题一定要处理好.

2.问题实践

2.1.斐波那契数列:

斐波那契数列是动态规划中最简单的一件问题也是最经典的一件问题 原问题看斐波那契数列
看完后我们可以知道斐波那契数列的数值为1 1 2 3 5 8 ...... 它的递推方法我们也可以看出就是第n个值=第n - 1个值+第n - 2个值除此之外它的第0个值=0 第1个值=1 在此我们列出它的公式:

$F (0) = 0\tag{1}$

$F(1) = 1 \tag{2}$

$F(N) = F(N - 1) + F(N - 2)\tag{3} \\ N \geq 2$

(像不像一架飞机👍👍👍）

注意在这里我们处理了边界问题避免了答案出错.

观看代码

在这里我们将代码搬上来:

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    int n; // 先写出我们需要查找的项数
    cin >> n; //输入查找的项数
    vector<int>DP(n + 1);//创建动态规划数组
    DP[0] = 1; DP[1] = 1; DP[2] = 1;//根据定义，斐波那契数列的第1项和第2项都为1 第0项为0
    for(int i = 3;i <= n;i++){//从第3个项数开始循环
        DP[i] = DP[i - 1] + DP[i - 2];//递推公式在此 f[n] = f[n - 1] + f[n - 2]
    }
    cout << DP[n] << "\n";//输出查找到的项数
    return 0;
}

代码讲解

在这段程序中的核心代码如下:

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

中间的一行代码就是我们最最最主要的代码我们将其称之为状态转移方程 它可以说是这道题之中最关键的代码但它的组成便是建立在递推和记忆化搜索之上我们只要以最优子结构方式一步一步的去进行推算最后再得到答案这种代码的生成便是很好体现了动态规划的主题思想其以非常简洁的方式将其写出.

所以动态规划以记忆和重新使用的方式大大提高了代码的时间效率以至于不让代码时间超时这便是拿空间换时间的精确体现.

动态规划是一种典型的拿空间换时间的思想（毕竟现在的社会时间成本比空间成本高太多了）————————此话引自Macw07老师一文讲清动态规划的本质中的感叹

代码的启发

从这篇代码中我们可以看出在记忆过某个子问题后and可以转移到下一个状态时子问题的状态就不会再去改变这就说明了一个问题就是动态规划不具有后效性 也可以说不具有后效性的算法才可以不去重复计算子问题也就可以更加节省时间.

递归和动态规划

虽然说递归和动态规划有着某种相同之处但细分来看它们还是有不同之处的:

递归通过自己调用自己的方式将整个问题划分为子问题再以重复计算的方式达到题目目标效率低下.
动态规划(DP) 通过将整问题划分为子问题随后再记忆已完成的子问题避开重复计算的可能从而达到目标效率超高（在这里我不是踩一捧一只是将两种算法进行比较).

在某种情况下你可以将带有记忆化的递归 视为动态规划.

分治思想和动态规划

动态规划的核心和分治思想的核心有点相似它们都与子问题有关都会把整问题分成多个局部问题但分开看我们可以找到细致的区别:

分治思想主要解决的问题还是子问题不重叠 它的算法强度并不高.
动态规划主要解决的问题还是子问题重叠 在解决这类问题时它的用处很广泛.

在解决子问题重叠问题上 DP时一个更好的选择.

模板代码

以下为无注释版代码:

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    int n;
    cin >> n;
    vector<int>DP(n + 1);
    DP[1] = 1; DP[2] = 1;
    for(int i = 3;i <= n;i++){
        DP[i] = DP[i - 1] + DP[i - 2];
    }
    cout << DP[n] << "\n";
    return 0;
}

做题时间

以下为斐波那契数列练习题:
A.7297 兔子数列
 A21007.月落乌啼算钱（斐波那契数列）
A21013.斐波那契数列

2.2爬楼梯

A想要爬上一层楼梯楼梯共有n格台阶 A可以走一格或两格请帮A想一想 A要爬上第n格有着多少种方法呢?
这种题目也是一道动态规划的经典例题 可惜许多初学者都不会做这样的题目根据第一题的经验我们一起来做一下这道题目.

首先我们以假设的方式去找出它的递推方法 我们假设要走到第5格台阶那么唯一能走到的便只有两种方法:
1.从第4格走到第5格.
2.从第3格走到第5格.

这可以说明一件事便是一个台阶和它前两个台阶有着关联（无后效性）那么我们也就可以推测上到第n格台阶的方案数就是上到前两格台阶的方案数这样我们就可以列出公式:

$F(0) = 0\\ F(1) = 1\\ F(2)= 2\\ F(N) = F(N - 1) + F(N - 2);\\ N\geq3$

(像不像一支宝剑👍👍👍)
注意要处理边界化问题其非常重要.

观看代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    int n;//创建我们需要查找的项数
    cin >> n;//输入
    vector<int>DP(n + 1);//创建动态数组
    DP[0] = 0; DP[1] = 1; DP[2] = 2;//根据公式f[0] = 0 f[1] = 1 f[2] = 2处理边界;
    for(int i = 3;i <= n;i++){//从第三个项数开始算起
        DP[i] = DP[i - 1] + DP[i - 2];//进行递推and记忆化
    }
    cout << DP[n] << "\n";//输出所查找项数的值
    return 0;
}

代码解析

此程序的的核心代码如下:

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

大家可能注意到了这段代码和原来的斐波那契数列的核心代码是一模一样的它的状态转移方程也同样是:

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

其实爬楼梯这道题就是斐波那契数列的进阶版 在我们刚刚列公式时就已经可以看出它的公式只比斐波那契多出了 $F(2) = 2$ 而已所以在这里我们不多讲述.

模板代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    int n;
    cin >> n;
    vector<int>DP(n + 1);
    DP[0] = 0; DP[1] = 1; DP[2] = 2;
    for(int i = 3;i <= n;i++){
        DP[i] = DP[i - 1] + DP[i - 2];
    }
    cout << DP[n] << "\n";
    return 0;
}

做题时间

A30913.爬楼梯
 A30652.【递归】【入门】爬楼梯
 U36981.上楼梯

2.3数字金字塔

顺推法

有一座用数字做成的金字塔金字塔的第 $n$ 层有着 $n$ 个数字从最顶部开始请你找出一条路线可以使此路的权值达到最大样例如下:

5//输入层级数
     1
    2 3
   4 5 6
  7 8 9 10
11 12 13 14 15

答案:

35
1 => 3 => 6 => 10 => 15

在这道题中许多码农会被其独特的输入给震惊到但不要怕我们一起以解决动态规划的步骤与去两道题带给我们的经验一起做一做.

在这里我们可以想到从第一层开始一层一层的推下去这样做的方法也可以达到我们想要的目标这种方法叫做顺推法 同时由于我们在往下走时只能选择两条路像是从第一层的1向第二层走时我们就只可以挑选2或是3 在每一层中我们都需要挑选一个数字从而达到最大权值这才是问题所在.
那么如果从顶层开始计算我们就要以下一层的某个阶段去看还需要进行记忆化和最优子结构 在每个阶段中都需要记录其线路的最大权值我们来举个例子:

就以上面的数字金字塔来说我们将目光投向第2层这其中有着一个权值2及3 当线路到达了2时这条线路的总权值为1 + 2 = 3 而线路经过3时线路的总权值为1 + 3 = 4 这时我们就已经将总权值给记录下来了在记录下来后我们再去看下一层的权值.

以这样的方式我们便可以列出公式就是将自己上面最大的一个总权值加上自己的权值.
我们以 $dp[i][j]$ 表示每个状态其中 $i$ 表示层数 $j$ 表示列数（第 $i$ 行的第 $j$ 个数字） $w[i][j]$ 表示此阶段的权值我们列出下面公式:

$dp[i][j] = max(dp[i - 1][j - 1],dp[i - 1][j ]) + w[i][j]\\ dp[1][1] = w[1][1]$

你发现什么了吗?
没错就是我们的处理边界问题（不要忘记哦).

在列出公式后我们写出程序:

观看代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    int n; 
    cin >> n;//输入层级数
    vector<vector<int>>a(n + 1,vector<int>(n + 1)),dp(n + 1,vector<int>(n + 1));//创建dp数组和数字金字塔数组
    for(int i = 1;i <= n;i++){//循环层级数次
        for(int j = 1;j <= i;j++){//循环此层级数次
            cin >> a[i][j];//输入数字金字塔
        }
    }
    dp[1][1] = a[1][1];//进行边界化处理
    for(int i = 2;i <= n;i++){//从第2行开始计算
        for(int j = 1;j <= i;j++){//每一行的每一个阶段都循环一次
            dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - 1]) + a[i][j];//核心状态转移方程 判断上面哪条线路的总权值最大 便添加到此dp阶段中（需要加上其本身的权值）
        }
    }
    int MAX = 0;//创建一个max变量
    for(int i = 1;i <= n;i++){//在最后一行循环
        MAX = max(MAX,dp[n][i]);//max变量取最后一行的最大总权值
    }
    cout << MAX << "\n";//输出
    return 0;
}

代码讲解

这篇程序的核心代码如下:

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

在 $for$ 循环中的一句代码便是整篇程序中的状态转移方程此方程的意义在上面已经讲述过因此We are talk anymore~~~~~~

逆推法

请不要以为这就结束了我们其实还有一种方法去解决此问题我们将其称之为倒推法.
倒推法的思想是从最底部开始推起以最优子结构和记忆化的方式一直到第1层 这样有一个好处就是在最后找到最大总权值时不用判断哪个更大只需将 $dp[1][1]$ 输出就好了 这就是好处但坏处就是在开始编写时我们需要把 $dp[n][i]$ 都添加上 $w[n][i]$ 的权值 这样才可以进行第 $n - 1$ 层的推算.

而它的公式与上一个顺推法有些许不同由于它是从下一直往上推断所以其阶段是以上面的权值判断下方的线路总权值（没听懂的同学可以借助公式理解此话）.
以 $n$ 表示为层级数 $dp[i][j]$ 表示每个状态其中 $i$ 表示层数 $j$ 表示列数（第 $i$ 行的第 $j$ 个数字） $w[i][j]$ 表示此阶段的权值我们将公式列出:

$dp[i][j] = max(dp[i + 1][j],dp[i + 1][j -1]) + w[i][j] \\ dp[n][j] = w[n][j]$

你发现了吗我们这次列出的公式还是进行了边界化处理所以说在列出公式时我们应该敏锐的察觉到处理边界这件事情.

观看程序

在列出公式之后我们列出程序:

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    int n;
    cin >> n;//输入层级数
    vector<vector<int>>a(n + 1,vector<int>(n + 1)),dp(n + 1,vector<int>(n + 1));//创建dp数组和数字金字塔数组
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= i;j++){
            cin >> a[i][j];//输入金字塔数组
        }
    }
    for(int i = 1;i <= n;i++){
        dp[n][i] = a[n][i];//为第n层的所有dp阶段添加权值
    }
    for(int i = n - 1;i >= 1;i--){//从第n - 1层开始计算
        for(int j = 1;j <= i;j++){//每层的权值都需要循环一遍
            dp[i][j] = max(dp[i + 1][j],dp[i + 1][j + 1]) + a[i][j];//状态转移方程 判断上面哪条线路的总权值最大 便添加到此dp阶段中（需要加上其本身的权值）
        }
    }
    cout << dp[1][1] << "\n";//输出第一层的dp阶段中的全局最大总权值
    return 0;
}

代码讲解

代码核心:

    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= i;j++){
            cin >> a[i][j];
        }
    }
    ......
     for(int i = n - 1;i >= 1;i--){
        for(int j = 1;j <= i;j++){
            dp[i][j] = max(dp[i + 1][j],dp[i + 1][j + 1]) + a[i][j];
        }
    }

你应该看出来了在这一次我们罗列了两个 $for$ 循环作为程序核心这两步代码在上面的意义已经讲述因此 We are talk anymore too.

模板代码

数学金字塔（顺推法）:

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    int n; 
    cin >> n;
    vector<vector<int>>a(n + 1,vector<int>(n + 1)),dp(n + 1,vector<int>(n + 1));
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= i;j++){
            cin >> a[i][j];
        }
    }
    dp[1][1] = a[1][1];
    for(int i = 2;i <= n;i++){
        for(int j = 1;j <= i;j++){
            dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - 1]) + a[i][j];
        }
    }
    int MAX = 0;
    for(int i = 1;i <= n;i++){
        MAX = max(MAX,dp[n][i]);    
    }
    cout << MAX << "\n";
    return 0;
}

数字金字塔(逆推法）:

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    int n;
    cin >> n;
    vector<vector<int>>a(n + 1,vector<int>(n + 1)),dp(n + 1,vector<int>(n + 1));
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= i;j++){
            cin >> a[i][j];
        }
    }
    for(int i = 1;i <= n;i++){
        dp[n][i] = a[n][i];
    }
    for(int i = n - 1;i >= 1;i--){
        for(int j = 1;j <= i;j++){
            dp[i][j] = max(dp[i + 1][j],dp[i + 1][j + 1]) + a[i][j];
        }
    }
    cout << dp[1][1] << "\n";
    return 0;
}

练习时间

A627.数字三角形
 A7930.数字金字塔
 A22681.数字三角形 Number Triangles

2.4最长公共子序列

给定两个字符串求出这两个字符串的最长公共子序列LCS 这里的子序列不需要连续但一定要保持顺序.
样例:

A = "ABCDEFG" B = "ACEG"
ANSWER = 4 LCS = "ACEG"

A = "LAKERS" B = "WOARRIORS"
ANSWER = 2 LCS = "RS"

这道题与前面的题目难度有一些不同我们顺着思路一起来做一做这道题目.
我们以递推的方式去想一想考察一下两个字符串的前缀根据每次都一步一步的去判断最长公共子序列的方式我们便可以推出状态的表示方法为 $A[1 => i] and B[1 => j]$ （这里指的是从 $a[1]$ 至 $a[i]$ $b[1]$ 至 $b[i]$ 及 $A$ 的前 $i$ 个字符和 $B$ 的前 $j$ 个字符）以这样的方式去定义每个阶段是目前的题目是最好的解决方法.

但如果someone问我为什么我们要这么定义的话我还真回答不上来但别担心只要这么定义就好了只是将其认知为这样的方法更好用就ok了但在我观看完Macw07老师的一文讲清动态规划的本质后发现这种问题还会有理由在这里我简要阐述一下 Macw07老师的观点（作者本人非常认同老师的想法小生不才若想学习到更多知识可以点击链接去观看一下Macw07老师的原话）:

Q1:为什么要将每个阶段定义为 $A[1 => i]$ 和 $B[1 => j]$

R1:递归思想的启发

如同上楼梯一般在我们知道了 $A[i => i - 1]andB[j =>j - 1]$ 的最长公共子序列后那我们也可以根据 $A[i - 1]andB[j - 1]$ 的关系去判断 $A[1 => i]andb[1 => j]$ 的最长公共子序列.
将整个字符串已不断增加前缀的方式去判断 $LCS$ 是一个很好的方法.

R2:易于表示动态变化

算法只需表示当前情况 不必考虑未来.
动态规划的核心避免重复计算通过子问题的答案推出最终答案.

Q2:为何选择子字符串的前缀

R1:动态规划的特性

动态规划从最小的问题开始求解而前缀是自然的分解方式：

对于 $A[1 => i]and B[1 => j]$ 最小的子问题是 $i=0 or j=0$ 即两个字符串中任意一个为空时 $LCS$ 长度为 0
从空字符串到完整字符串的逐步扩展非常符合动态规划的思路.

R2:逐步拓展问题规模

通过管理问题规模我们可以更好的向前发展在一个二维数组 $dp[i][j]$ 之中我们可以以小问题构造出大问题:

如果我们从其他部分（如整个字符串开始下手的话）我们将会碰到麻烦出现问题不能很好的去解决问题但利用前缀的方式可以只判断最后一个字符再结合原来的最长公共子序列结果就能够解决当前的子问题.

以上就是全部理由在结束观看之后细心的同学已经可以推出此问题的公式（状态转移方程）了但可能大家没有做到......don't worry 在这一步我们开始探索公式.

我们考虑多种情况一步步的推算公式.

Scene1: $A[i - 1] == B[j - 1]$

在这里因为两个字符相同所以它们可以加入最长公共子序列这时在dp动态数组上此次 $dp[i][j] = dp[i - 1][j - 1] + 1$ (注:这里的 $dp[i][j]$ 表示字符串 $A$ 的前 $i$ 个字符和字符串 $B$ 的前 $j$ 个字符的最长公共子序列的长度.

Scene2: $A[i - 1] != B[j - 1]$

因为两个字符不相同我们不可以将它们加入最长公共子序列这是在dp动态数组上此次dp动态数组需要判断前一个 $LCS$ 的大小所以在这里我们的dp数组只能决定是排除 $A$ 的最后一个字符还是排除 $B$ 的最后一个字符以找到更长的公共子序列因此可得 $dp[i][j] = max(dp[i - 1][j],dp[i][j - 1])$ .
$dp[i-1][j]$ 表示排除 $A$ 的最后一个字符后字符串 $A$ 的前 $i-1$ 个字符和字符串 $B$ 的前 $j$ 个字符的最长公共子序列的长度.
$dp[i][j-1]$ 表示排除 $B$ 的最后一个字符后字符串 $A$ 的前 $i$ 个字符和字符串 $B$ 的前 $j-1$ 个字符的最长公共子序列的长度.
我们以这种方式得到最长公共子序列的最大值后即可输出.

观看代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    string a,b;
    cin >> a >> b;
    vector<vector<int>>dp(a.size() + 1,vector<int>(b.size() + 1));
    for(int i = 1;i <= a.size();i++){
        for(int j = 1;j <= b.size();j++){
            if(a[i - 1] == b[j - 1]){
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }else{
                dp[i][j] = max(dp[i - 1][j],dp[i][j - 1]);
            }
        }
    }
    cout << dp[a.size()][b.size()] << "\n";
    return 0;
}

此代码不做讲解自行理解.

2.5背包问题

请大家去看一看我之前写过的一篇帖子链接如下:
关于动态规划（背包问题）讲解
在这里我们不做讲解.

刷题时间

A21154.物品选取
 A22579.部分背包问题
 A628.钞票问题

在这里面我们讲解了六种不同的动态规划题目在很多的 C++ 竞赛之中我们总是可以发现动态规划的身影其算法难度非常高需要每位同学都多加练习才能熟练的掌握此算法的核心.

后话

对于动态规划我认为还是要去进行更多的刷题在做多题目过后就会找到规律很多题目都可以用公式解决很多题目实际上都是有迹可循的我也可以理解每个人对待这类算法的感觉动态规划这个算法的核心确实较为难懂但只要多加练习每个人都可以学会并且运用动态规划.

以上就是我们本篇文章的主要内容了希望看到这里的同学都可以为这篇文章点一个小赞（只需要动一下鼠标就能为我带来很大的鼓励求求了).

在此鸣谢:
Macw07老师的精选文章一文讲清动态规划的本质此文章对这篇动态规划讲解有着很高的帮助and帮我理清了文章结构其内部参考文献非常有干货列在文章末尾.
Ysjt | 深 ™老师的精选文章#创作计划#动态规划【C++优质版】也对此动态规划讲解文章有着很大帮助为我创作这篇帖子提供了好的思路.
还有很多位ACGO社区的小伙伴们的帖子也为我提供了很多的价值在此感谢每一个人的帮助.
参考文献:
GeeksforGeeks. (n.d.). Dynamic Programming. Retrieved