什么是动态规划？
动态规划，英文名为Dynamic Programming，又称DP（当然小写的dp也行），是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。由于动态规划并不是某种具体的算法，而是一种解决特定问题的方法，因此它会出现在各式各样的数据结构中，与之相关的题目种类也更为繁杂。在 OI 中，计数等非最优化问题的递推解法也常被不规范地称作 DP。
dp的重要性？
在作者打过的镇赛,区赛乃至GDOI,CSP中，dp一直是常考的东西。所以学会dp尤为关键。
举个例子，2017-2022年的镇赛,区赛中dp常作为压轴题出现，甚至NHOI 2022中T5,T6都是dp。
动态规划入门
先来看这样一道题：P1216 [USACO1.5][IOI1994]数字三角形 Number Triangles（学校OJ 1351）
尽管这道题是IOI的，但不妨碍我们切掉
想必有人会考虑贪心，即如果左边大一点就往左边走，右边大一点就忘右边走。看到给出的样例，就知道这个方法不可行了。如果还想继续从第二大值，第三大值等等情况考虑，你就发现深陷其中无法自拔了。
接下来我们通过这道例题详细分析以下如何做一道动态规划的题目：
Step 1：设计状态
对于动态规划，设计一个状态是做题的第一步。这里初学者可能不知道状态是什么，但是请先耐心看下去。
比如这道题，我们定义一个二维数组 \(f_{i,j}\) 表示的是从起点 \((1,1)\) 走到当前点 \((i,j)\) 的最大值。这里 \(f_{i,j}\) 就表示一个状态。
一般而言，设计的状态通常都是由所需要的答案决定，如本题需要的就是从起点 \((1,1)\) 走到终点的最大值。
请注意，设计出一个好的状态非常重要！请注意，设计出一个好的状态非常重要！请注意，设计出一个好的状态非常重要！（重要的话说三遍！！！）
Step 2：设计转移方程
显然，设计好一个状态后，我们需要考虑这个状态的答案应该如何计算得到的，即设计转移方程。
例如本题，我们可以画一个表格分析：
| \((i-1,j-1)\) | \((i-1,j)\) |
|---|---|
| \((i,j-1)\) | \((i,j)\) |
显然，我们发现，有两种可以走到当前点 \((i,j)\) 的方法：
- \((i-1,j-1)\xrightarrow{}(i,j)\)，这时答案应该为从 \((1,1)\) 走到 \((i-1,j-1)\) 的最大值再加上当前取 \((i,j)\) 格子的价 \(a_{i,j}\)，即\(f_{i-1,j-1}+a_{i,j}\)。
- \((i-1,j)\xrightarrow{}(i,j)\)，这时答案应该为从 \((1,1)\) 走到 \((i-1,j)\) 的最大值再加上当前取 \((i,j)\) 格子的价 \(a_{i,j}\)，即\(f_{i-1,j-1}+a_{i,j}\)。
我们要的是最大值，所以对两种情况取一个最大值即可得到当前状态 \(f_{i,j}\) 的答案。即
\[f_{i,j}=\max(f_{i-1,j-1}+a_{i,j},f_{i-1,j}+a_{i,j}) \]或者可以写成
\[f_{i,j}=\max(f_{i-1,j-1},f_{i-1,j})+a_{i,j} \]f[i][j]=max(f[i-1][j-1]+a[i][j],f[i-1][j]+a[i][j]);//写法1
f[i][j]=max(f[i-1][j-1],f[i-1][j])+a[i][j];//写法2
Step 3：确定答案
根据题意，我们知道终点可以是最后一行的任意一个格子，即 \(f_{n,i}\) ，这里的 \(i\) 可以是 \(1\sim n\) 的其中一个，即 \(1\le i\le n\)。不妨枚举这个 \(i\)，然后对于所有的 \(f_{n,i}\) 求一个最大值即可。
Code Time:
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n;
int a[N][N],f[N][N];
int ans;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
scanf("%d",&a[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
f[i][j]=max(f[i-1][j-1],f[i-1][j])+a[i][j];
for(int i=1;i<=n;i++)ans=max(ans,f[n][i]);
printf("%d",ans);
return 0;
}
总结
这是我总结的dp的三步走方案，熟记这三个步骤你可以完成大部分的简单dp，从而入门dp。
对于这道题的一个题外话
对于 Step 2:设计转移方程 不一定有唯一的答案，如本题可以用倒推的方案去设计，即从这两个方案入手。具体代码就不展示了，留给读者自行思考吧。
下面给几道例题巩固一下：
-
Frog 1（学校OJ 1352）
-
Frog 2（学校OJ 1353）
-
P1115 最大子段和（学校OJ 1239）
-
P2800 又上锁妖塔（学校OJ1355）