线性DP
数字三角形【898】
（参考AcWing 898. 【算法基础课】数字三角形（线性DP） - AcWing）
#include<bits/stdc++.h>
using namespace std;
const int N=509;
int x[N][N], dp[N][N]; // x存储输入的三角形数，dp[i][j]表示从根节点到i，j结点的长度
int n; // 三角形的层数int main() {cin >> n; // 输入三角形的值for (int i = 1; i <= n; i++) {for (int j = 1; j <= i; j++) {cin >> x[i][j];}}// 初始化dp数组memset(dp, -0x3f3f3f3f, sizeof dp); // 将dp数组的每个元素都设置为一个很小的值dp[1][1] = x[1][1]; // 初始化起点// 动态规划计算最大路径和for (int i = 2; i <= n; i++) {for (int j = 1; j <= i; j++) {dp[i][j] = max(dp[i-1][j-1] + x[i][j], dp[i-1][j] + x[i][j]);}}// 找到最后一行（第n行）的最大值dp[n][i]int result = -0x3f3f3f3f;for (int i = 1; i <= n; i++) {result = max(result, dp[n][i]);}cout << result; return 0;
}
最长上升子序列【895】
（题解参考AcWing 898. 数字三角形 - AcWing）
#include<bits/stdc++.h>
using namespace std;const int N = 1010;
int dp[N]; // dp[i] 表示以第i个元素结尾的最长递增子序列的长度
int x[N]; // x[i] 存储输入的数列
int n; int main() {cin >> n; for(int i = 1; i <= n; i++) cin >> x[i]; for(int i = 1; i <= n; i++) {dp[i] = 1; // 初始化dp[i]为1，表示每个元素单独一项至少有一个递增子序列（即它自己）// 遍历前面的元素，查找是否可以扩展递增子序列for(int j = 1; j < i; j++) {// 如果x[j]小于x[i]，说明可以在x[j]后面接上x[i]if(x[j] < x[i]) dp[i] = max(dp[i], dp[j] + 1); // 更新dp[i]，取最大值，表示以x[i]结尾的最大递增子序列长度}}// 计算整个数列中的最长递增子序列的长度int res = 0; for(int i = 1; i <= n; i++) res = max(res, dp[i]); cout << res; return 0;
}
最长公共子序列【897】
集合表示：f[i][j]：A前i个字符，B前j个字符的公共子序列 的集合 属性：maxlen
集合划分：
情况1：a[i],b[j] 均存在于 最长公共子序列中 (前提a[i]==b[j])
情况2：a[i] 在，b[j] 不在 （无前提）
情况3：a[i],b[j] 均不在 （无前提）
情况4：a[i]不在，b[j]在 （无前提）
需要 求得的是 max(情况1，情况2，情况3，情况4)
而：f[i-1][j-1]+1 可以表示情况1 --> a
f[i][j-1]=max(情况2,情况3) --> b
f[i-1][j]=max(情况3,情况4) --> c
所以我们最终只需要 求 max(a,b,c) 即可
#include<bits/stdc++.h>
using namespace std;const int S = 1010; // 定义最大字符串长度
int n, m;
int dp[S][S]; // dp数组，dp[i][j]表示s1前i个字符和s2前j个字符的最长公共子序列长度
char s1[S], s2[S]; // 存储两个字符串int main()
{cin >> n >> m; // 输入第一个字符串for (int i = 1; i <= n; i++) cin >> s1[i];// 输入第二个字符串for (int i = 1; i <= m; i++) cin >> s2[i];// 动态规划计算最长公共子序列for (int i = 1; i <= n; i++) // 遍历第一个字符串的每一个字符{for (int j = 1; j <= m; j++) // 遍历第二个字符串的每一个字符{// 如果s1[i] == s2[j]，则说明这两个字符可以匹配，最长公共子序列长度加1if (s1[i] == s2[j]) dp[i][j] = dp[i - 1][j - 1] + 1;else{// 如果s1[i] != s2[j]，则选择去掉s1的一个字符或去掉s2的一个字符// 最大的公共子序列长度来自于去掉一个字符的情况,这里求maxdp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}}}cout << dp[n][m];return 0;
}
最短编辑距离【902】
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
char a[N],b[N];
int n,m;
int dp[N][N];
int main()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i];cin>>m;for(int i=1;i<=m;i++) cin>>b[i];for(int i=0;i<=n;i++) dp[i][0]=i;for(int j=0;j<=m;j++) dp[0][j]=j;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1);if(a[i]==b[j]) dp[i][j]=min(dp[i][j],dp[i-1][j-1]);else dp[i][j]=min(dp[i][j],dp[i-1][j-1]+1);}}cout<<dp[n][m];return 0;
}区间DP
石子合并【282】
#include<bits/stdc++.h>
using namespace std;const int N = 310;
// dp[i][j]表示将区间[i, j]的数合并为一堆的最小代价
int dp[N][N];
// s数组用于存储前缀和，s[i]表示前i个数的和
int s[N];
int n;
int main()
{cin >> n;// 计算前缀和for (int i = 1; i <= n; i++){cin >> s[i];s[i] += s[i - 1];}// 枚举区间长度len，从2开始，长度为1时不需要合并，代价为0for (int len = 2; len <= n; len++){// 枚举区间的左端点j，保证区间[j, j + len - 1]不超出范围for (int j = 1; j + len - 1 <= n; j++){// 确定区间的左右端点int l = j;int r = j + len - 1;// 初始化dp[l][r]为一个较大的值，方便后续取最小值操作dp[l][r] = 1e9;// 遍历区间[l, r]的分隔点k，尝试不同的合并方式for (int k = l; k <= r - 1; k++){// 更新dp[l][r]的值，取当前值和通过分隔点k合并的代价的最小值// dp[l][k]表示将区间[l, k]合并为一堆的最小代价// dp[k + 1][r]表示将区间[k + 1, r]合并为一堆的最小代价// s[r] - s[l - 1]表示将两堆合并时需要额外加上的代价，即当前区间内所有数的和dp[l][r] = min(dp[l][k] + dp[k + 1][r] + s[r] - s[l - 1], dp[l][r]);}}}// 整个区间[1, n]合并为一堆的最小代价cout << dp[1][n];return 0;
}所有的区间dp问题枚举时，第一维通常是枚举区间长度，并且一般 len = 1 时用来初始化，枚举从 len = 2 开始；第二维枚举起点 i （右端点 j 自动获得，j = i + len - 1）模板代码如下：
for (int len = 1; len <= n; len++) { // 区间长度for (int i = 1; i + len - 1 <= n; i++) { // 枚举起点int j = i + len - 1; // 区间终点if (len == 1) {dp[i][j] = 初始值continue;}for (int k = i; k < j; k++) { // 枚举分割点，构造状态转移方程dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + w[i][j]);}}
}