#创作计划#关于动态规划（DP）全面讲解
2025-08-17 08:59:17
发布于：安徽
关于动态规划的全面讲解
Khalil Fong的动态规划讲解 前言———————————————————————动态规划（Dynamic Programming） 从它诞生以来 就一直是一个C++中的核心算法 但因其的难度性劝退了众多的码农 动态规划不是以其的数学推算或是程序编写能力出众 而是它就像是一种从思维演算到题目建模的一类编程算法.
这篇文章以动态规划出发 向各位解释其DP的本质 运用范围 核心特点 and 解题方法&思路 向各位提供超详细的动态规划解析.
1.基础动态规划
动态规划的核心特点便是将一个大问题拆解成多个小问题 这些问题在逐步解决的同时不断地记录下来 这样就提高了解题效率 这两种方法便是动态规划中的划分子问题和记忆化搜索.
动态规划可以解决的问题多是像这两类:
1) 子问题重叠:
在划分完子问题后 发现有一些问题在递归时会出现步骤 or 答案重复计算的问题 这样做会使得时间和空间有一定浪费 可能单个子问题发生不是大事 但多个子问题发生此事可能会超时或超空间.
2) 最优子结构:
这类问题是以一个个子问题达到最优解 从而使全局都达到最优解 简单来说 就是让每一个局部问题都竭尽所能的达到最好 从而使全局都达到最好.
动态规划的核心
动态规划以子问题重叠 最优子结构 最优原理和无后效性闻名 前两个已经说过了 我们来讲一讲后面两个最优原理和无后效性的核心概念是由美国数学家 理查德·贝尔曼（Richard Bellman） 所提出的 他在20世纪50年代系统地发展了动态规划这一数学优化方法，并首次明确提出了最优化原理（Principle of Optimality）以及无后效性（Markovian property）的概念.
无后效性指在某个阶段(例如被确定已经有某个权值)被确定有着一个状态时 其阶段的状态就不会在改变了 也不会影响的后面的决策 只与现在的决策有关 也就是过去的事件不会影响未来 只与目前有关联.
最优原理指在每一个子问题中都达到最优的效果 从而使全局达到最好 最优性原理是动态规划里最重要的一块基石.
附 如何解决动态规划
解决动态规划这类的问题需要分多个步骤 思想如下:
step 1:确定level and step(层级和步骤）
以题目为准 我们把一个题目转换成多个子问题 又将一个子问题转换成多个子子问题 如俄罗斯套娃一般的细分下去 每一个需要解决的问题就是一种层级 对于每个DP问题来说 我们第一步要干的就是将一个大问题拆成多个小问题 在逐步解决每个局部问题 同时 我们还需要找到一个变量 能够把所有的小问题都串联在一起 在刚刚的斐波那契数列中 斐波那契数列的项数就是变量 它连接了每一个子问题.
step 2:找到状态转移方程
在划分完子问题后 我们要想一想一件事情 就是如何将所有的子问题给串联起来 我们得到了很多子问题 也得到了我们需要的变量 接下来就是使用变量 将子问题都串联到一起
我们需要使用一句代码完成这件事情 那这时 状态转移方程就派上用场了.
（我们可以提前列出一个公式 以其为中心编写核心程序).
状态转移方程和子问题及变量都密不可分 所以 我们在编写状态转移方程时需要多用上变量改变子问题 最好包括到所有的变量 以便为后面的程序提供更多可能.
step 3:处理边界问题
在找到状态转移方程后 我们的思路构建已经完成一大半了 但一些边界问题我们还是需要处理一下 比如说斐波那契数列中的初始化问题 和这样的边界值处理 虽然这是一件极小的事情 但在这类地方犯错误就会引起蝴蝶效应 导致后面的值一错再错 so这样的问题一定要处理好.
2.问题实践
2.1.斐波那契数列:
斐波那契数列是动态规划中最简单的一件问题也是最经典的一件问题 原问题看斐波那契数列
看完后 我们可以知道 斐波那契数列的数值为1 1 2 3 5 8 ...... 它的递推方法我们也可以看出 就是第n个值=第n - 1个值+第n - 2个值 除此之外 它的第0个值=0 第1个值=1 在此我们列出它的公式:
(像不像一架飞机👍👍👍）
注意 在这里 我们处理了边界问题 避免了答案出错.
观看代码
在这里 我们将代码搬上来:
#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格台阶的方案数就是上到前两格台阶的方案数 这样 我们就可以列出公式:
(像不像一支宝剑👍👍👍)
注意要处理边界化问题 其非常重要.
观看代码
#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];
其实爬楼梯这道题就是斐波那契数列的进阶版 在我们刚刚列公式时就已经可以看出 它的公式只比斐波那契多出了而已 所以在这里我们不多讲述.
模板代码
#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数字金字塔
顺推法
有一座用数字做成的金字塔 金字塔的第层有着个数字 从最顶部开始 请你找出一条路线 可以使此路的权值达到最大 样例如下:
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 这时 我们就已经将总权值给记录下来了 在记录下来后 我们再去看下一层的权值.
以这样的方式 我们便可以列出公式 就是将自己上面最大的一个总权值加上自己的权值.
我们以表示每个状态 其中表示层数 表示列数（第行的第个数字）表示此阶段的权值 我们列出下面公式:
你发现什么了吗?
没错 就是我们的处理边界问题（不要忘记哦).
在列出公式后 我们写出程序:
观看代码
#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],max(dp[i - 1][j + 1],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],max(dp[i - 1][j + 1],dp[i - 1][j - 1])) + a[i][j];
}
}
在循环中的一句代码便是整篇程序中的状态转移方程 此方程的意义在上面已经讲述过 因此We are talk anymore~~~~~~
逆推法
请不要以为这就结束了 我们其实还有一种方法去解决此问题 我们将其称之为倒推法.
倒推法的思想是从最底部开始推起 以最优子结构和记忆化的方式一直到第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];//输入金字塔数组
}
}
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],max(dp[i + 1][j + 1],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],max(dp[i + 1][j + 1],dp[i + 1][j - 1])) + a[i][j];
}
}
你应该看出来了 在这一次 我们罗列了两个循环作为程序核心 这两步代码在上面的意义已经讲述 因此 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],max(dp[i - 1][j + 1],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],max(dp[i + 1][j + 1],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"
这道题与前面的题目难度有一些不同 我们顺着思路 一起来做一做这道题目.
我们以递推的方式去想一想 考察一下两个字符串的前缀 根据每次都一步一步的去判断最长公共子序列的方式我们便可以推出状态的表示方法为（这里指的是从至 至 及的前个字符和的前个字符） 以这样的方式去定义每个阶段是目前的题目是最好的解决方法.
但如果someone问我为什么我们要这么定义的话我还真回答不上来 但别担心 只要这么定义就好了 只是将其认知为这样的方法更好用就ok了 但在我观看完Macw07老师的一文讲清动态规划的本质后 发现这种问题还会有理由 在这里 我简要阐述一下 Macw07老师的观点（作者本人非常认同老师的想法 小生不才 若想学习到更多知识 可以点击链接去观看一下Macw07老师的原话）:
Q1:为什么要将每个阶段定义为和
R1:递归思想的启发
- 如同上楼梯一般 在我们知道了的最长公共子序列后 那我们也可以根据的关系去判断的最长公共子序列.
- 将整个字符串已不断增加前缀的方式去判断是一个很好的方法.
R2:易于表示动态变化
-
算法只需表示当前情况 不必考虑未来.
-
动态规划的核心避免重复计算 通过子问题的答案推出最终答案.
Q2:为何选择子字符串的前缀
R1:动态规划的特性
动态规划从最小的问题开始求解 而前缀是自然的分解方式：
- 对于 最小的子问题是 即两个字符串中任意一个为空时 长度为 0
- 从空字符串到完整字符串的逐步扩展非常符合动态规划的思路.
R2:逐步拓展问题规模
通过管理问题规模 我们可以更好的向前发展 在一个二维数组之中 我们可以以小问题构造出大问题:
- 如果我们从其他部分（如整个字符串开始下手的话） 我们将会碰到麻烦 出现问题 不能很好的去解决问题 但利用前缀的方式 可以只判断最后一个字符 再结合原来的最长公共子序列结果 就能够解决当前的子问题.
以上就是全部理由 在结束观看之后 细心的同学已经可以推出此问题的公式（状态转移方程）了 但可能大家没有做到......don't worry 在这一步 我们开始探索公式.
我们考虑多种情况 一步步的推算公式.
Scene1:
在这里 因为两个字符相同 所以它们可以加入最长公共子序列 这时在dp动态数组上 此次(注:这里的 表示字符串 的前 个字符和字符串 的前 个字符的最长公共子序列的长度.
Scene2:
因为两个字符不相同 我们不可以将它们加入最长公共子序列 这是在dp动态数组上 此次dp动态数组需要判断前一个的大小 所以在这里 我们的dp数组只能决定是排除的最后一个字符还是排除的最后一个字符 以找到更长的公共子序列 因此可得.
表示排除的最后一个字符后 字符串的前个字符和字符串的前个字符的最长公共子序列的长度.
表示排除的最后一个字符后 字符串的前个字符和字符串的前个字符的最长公共子序列的长度.
我们以这种方式得到最长公共子序列的最大值后即可输出.
观看代码
#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.6最长上升子序列
给点一个数列A 请你在此数列中找出一个最大的最长上升子序列（意为非递减序列）.
样例：
n = 5
A = {1 2 3 4 5}
answer = 5
n = 6
A = {1 2 5 4 6 3}
answer = 4
这道题的难度相较于其文章前面的题型都提升了一定的难度 让我们一起来解一下这道题.
我们以拆分出子问题的方式去做出此题 以每个元素做单位 将这个元素前面看成此数列的一个子串 逐步的去分析最长上升子序列的长度.
我们以这样的方式去进行思考之后就会发现 每一个元素似乎都有可能变成最长上升子序列的最后一个元素 包括第一个也不例外 所以 在输出答案的时候 我们就要判断每一个元素前面的最长上升子序列的长度的最大值 同时 所有的元素都可以自成一个最长上升子序列 所以 在考虑边界化的时候 我们就要将所有的元素的初始值都化为1.
对于每个子串的最长上升子序列 我们判断其元素为末尾时 是否可以添加到前面的字串的最长上升子序列里 此时就需要判断此元素是否严格递增于前面的最长上升子序列 还需要判断总最长上升子序列的长度取决于以此元素为结尾的子串的最长上升子序列还是前面的子串的最长上升子序列加上现在的元素的长度 只要判断好这些 我们自然能够写出代码.
观看代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
int n;
cin >> n;
vector<int>a(n + 1),dp(n + 1);
for(int i = 1;i <= n;i++){
cin >> a[i];
dp[i] = 1;
}
for(int i = 1;i <= n;i++){
for(int j = 1;j < i;j++){
if(a[i] > a[j]){
dp[i] = max(dp[i],dp[j] + 1);
}
}
}
int Max = 0;
for(int i = 1;i <= n;i++){
Max = max(Max,dp[i]);
}
cout << Max << "\n";
return 0;
}
此代码不做讲解 大家自行观看.
2.7背包问题
请大家去看一看我之前写过的一篇帖子 链接如下:
关于动态规划（背包问题）讲解
在这里 我们不做讲解.
刷题时间
A21154.物品选取
A22579.部分背包问题
A628.钞票问题
在这里面 我们讲解了七种不同的动态规划题目 在很多的 C++ 竞赛之中 我们总是可以发现动态规划的身影 其算法难度非常高 需要每位同学都多加练习 才能熟练的掌握此算法的核心.
后话
对于动态规划 我认为还是要去进行更多的刷题 在做多题目过后就会找到规律 很多题目都可以用公式解决 很多题目实际上都是有迹可循的 我也可以理解每个人对待这类算法的感觉 动态规划这个算法的核心确实较为难懂 但只要多加练习 每个人都可以学会并且运用动态规划.
以上就是我们本篇文章的主要内容了 希望看到这里的同学都可以为这篇文章点一个小赞（只需要动一下鼠标就能为我带来很大的鼓励 求求了).
在此鸣谢:
Macw07老师的精选文章一文讲清动态规划的本质 此文章对这篇动态规划讲解有着很高的帮助and帮我理清了文章结构 其内部参考文献非常有干货 列在文章末尾.
Ysjt | 深 ™老师的精选文章#创作计划#动态规划【C++优质版】也对此动态规划讲解文章有着很大帮助 为我创作这篇帖子提供了好的思路.
还有很多位ACGO社区的小伙伴们的帖子也为我提供了很多的价值 在此感谢每一个人的帮助.
参考文献:
GeeksforGeeks. (n.d.). Dynamic Programming. Retrieved
Gupta, R. (2023). Mastering Dynamic Programming: A Step-by-Step Guide. Medium. Retrieved
Stanford University. (n.d.). Dynamic Programming. Retrieved
Stanford University. (2013). Dynamic Programming Lecture Notes (CS161). Retrieved
Bellman, R. (1966). Dynamic Programming. Science, 153(3731), 34–37. doi
有帮助，赞一个