动态规划学习笔记
2025-07-29 17:59:51
发布于：上海
注：学习过程参考书籍《算法竞赛》上册。
动态规划，用于需要求取全局最优解的问题。
一般这类问题具有两种特征：重叠子问题，最优子结构。
引入：斐波那契数列
斐波那契数列是一个递推数列。
其递推公式为：
这是一个初始版本：
#include<bits/stdc++.h>
using namespace std;
long long a[35];
int fib(int x){
if(x==1){
a[x]=1;
return 1;
}else if(x==2){
a[x]=1;
fib(1);
return 1;
}
a[x]=fib(x-1)+fib(x-2);
return a[x];
}
int main(){
int n;
cin>>n;
fib(30);
for(int i=1;i<=n;i++){
int x;
cin>>x;
cout<<a[x]<<'\n';
}
return 0;
}
斐波那契的运用场景是走楼梯。
一次可以走一阶或两阶楼梯，走到第x阶楼梯有多少种走法。
上方的代码时间复杂度不太好，使用DP可以优化其时间复杂度。
可以从前面提到的两个特性入手。
1.重叠子问题
指子问题是原大问题的小版本，计算步骤完全一样。
其次，计算大问题时，需要多次重复计算小问题。
斐波那契的计算过程大概是这样：
可以发现有很多重复计算。就进行了两次计算。
这就是重叠子问题。
用DP处理重叠子问题，每个子问题只计算一次，因而其效率高。
具体做法：首先分析得到最优子结构，然后用递推或带记忆化搜索的递归进行编程。
2.最优子结构
首先，大问题的最优解包含小问题的最优解；其次，可以用小问题的最优解推导出大问题的最优解。
这就是最优子结构。
在斐波那契数列中 ,这是斐波那契的最优子结构。
无后效性：
在DP中时常会提到无后效性。即只关心结果，不关心过程。
这跟重叠子问题有些关系。
在我已经计算出 和 后，我就会直接计算 ，而不是再去重新计算他们。
无后效性是DP的必要条件，只有这样才能降低时间复杂度。
处理DP中的大问题和小问题，有两种思路：自顶向下和自底向上。
1.自顶向下与记忆化
先考虑大问题，再把范围逐渐缩小。递归很直接的体现了这种思路。
为避免重复计算，可以在子问题解决时就保存结果，再次需要这个结果时，直接返回保存的结果即可。
这种存储已解决的子问题的结果的技术称为记忆化。
以斐波那契数列为例，代码如下：
#include<bits/stdc++.h>
using namespace std;
long long a[35];
int fib(int x){
if(a[x])return a[x];
if(x==1||x==2){
a[x]=1;
return 1;
}
a[x]=fib(x-1)+fib(x-2);
return a[x];
}
int main(){
int n;
cin>>n;
fib(30);
for(int i=1;i<=n;i++){
int x;
cin>>x;
cout<<a[x]<<'\n';
}
return 0;
}
时间复杂度为 。
2.自底向上与制表递推
这种方法与自顶向上完全相反，避免了使用递归编程。
先解决子问题，再递推到大问题。
通常通过填写表格来完成。
用for循环来逐步填写表格。
以斐波那契数列为例，代码如下：
#include<bits/stdc++.h>
using namespace std;
long long a[35];
int main(){
int n;
cin>>n;
a[1]=1;
for(int i=2;i<=30;i++){
a[i]=a[i-1]+a[i-2];
}
for(int i=1;i<=n;i++){
int x;
cin>>x;
cout<<a[x]<<'\n';
}
return 0;
}
自顶向下的优点是更容易理解问题的实质，而自底向上的优点是编码更直接。
0/1背包：
给定n种物品和一个背包，第 个物品的体积为 ，价值为 .
每个物品有两种选择：装入背包或不装。
这称为背包问题。
那么如何选择装入背包的物品，使装入背包的物品总价值最大？
题目：采药
这是一个0/1背包的模板。
0/1背包问题一般使用DP解决。
那么不妨先来探讨一下，为什么0/1背包问题可以用DP解决？
前面提到过使用DP解决的问题一般都有两种特征：
重叠子问题和最优子结构。
*重叠子问题的定义：指子问题是原大问题的小版本，计算步骤完全一样。
重叠子问题的体现：本题想问在有 时间，种草药时，可以采到的草药的最大价值。
这是大问题，那么小问题是什么？
由于涉及了两个变量，所以不能妄下定论，这是我的一个猜测：
那么假设所谓的子问题是这三种中的其中几个或全部，它们的计算步骤又是什么？
此问题暂且保留。
*最优子结构的定义：大问题的最优解包含小问题的最优解，可以用小问题的最优解推导出大问题的最优解。
此时对“计算步骤”的推断有了一些进展：大问题最优解由小问题推导。
那么如何推导？
假设我们现在想要直接求出在有 时间， 药草时的最大价值，且拥有所有与其相关的子问题的答案，如何推导？
联系上一道题目，斐波那契数列的推导是如何进行的？
很显然，采药与斐波那契数列的推导不太相似，但是可以试图用同样的格式进行列式。
这里的 表示的是在有 时间，种草药时，能获得的最大价值。
根据斐波那契的经验，大问题是由子问题的答案堆砌而成的，而所谓的子问题就是在大问题的变量上进行减法。
比如 就是 的子问题。
那么转移一下 和 中，是否会有 的子问题呢？
1.DP状态的设计
DP的状态是一个很抽象的概念。
前文中提到过”自底向上与制表递推“，表格需要一维或多维数组来呈现，那个数组就称为”状态“。
在本题中，引入一个 的二维数组 ，称为DP状态。
DP状态的定义是整个算法的核心，影响了后续的状态转移方程的构造，初始化等等步骤。
直接决定问题的可解性和效率。
而状态的具体设计，会和你需要的答案有一定的联系。
以本题为例：本题需要的答案是在有 时间， 株草药时，可以采到的草药的最大总价值。
那么有两个需要注意的变量：时间和草药数。
有帮助，赞一个