动态规划

动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法

由于动态规划并不是某种具体的算法，而是一种解决特定问题的方法，因此它会出现在各式各样的数据结构中，与之相关的题目种类也更为复杂

思想：

有一个事实，一条最优的路径，它的每一步决策都是最优的

因此一个子问题的的决策得到的最大（或最小）权值，用这个权值执行下一步决策，可以缩小问题的规模，将一个问题分成多个规模更小的问题

子问题间重叠的部分有可能会有很多，同一个子问题可能会被重复访问多次权，效率还是不高。可以把每个子问题的解储存起来，通过记忆化的方式限制访问顺序，确保每个子问题只被访问一次。

原理：

最优子结构
即，一个问题的最优解要求它的子问题也是最优解，具有最优子结构也可能是适合用贪心方法求解。
无后效性
已经求解的子问题，不会再受到后续决策的影响。
子问题重叠
如果有大量的重叠子问题，我们可以用空间将这些子问题的解存储下来，避免重复求解相同的子问题，从而提升效率。

步骤：

将原问题划分为若干阶段，每个阶段对应若干个子问题，提取这些子问题的特征（称之为状态）
寻找每一个状态的可能决策, 或者说是各状态间的相互转移方式（用数学语言描述就是状态转移方程）
按顺序求解每一个阶段的问题

在图论上，建立一个有向无环图，每一个状态对应图上一个节点，决策对应节点间的连边。这样的问题转换成图上寻找一个最值的问题。

关键是寻找状态转移方程，而状态转移方程的形成又是取决于数组（区间）的意义。

洛谷 P1216open in new window

这是一道 dp 入门题，其中这里 a[i][j] 表示从点(i, j)通过若干点走到底层，取值和的最大值
因此状态转移方程为a[i][j] += max(a[i + 1][j], a[i + 1][j + 1]);表示该点走到底取值的最大值

共有两个决策：

走到该点下方
走到该点右下方

那么两个决策的最大值就是最后的决策。

即满足最优子结构

#include <bits/stdc++.h>

using namespace std;
const int N = 1003;
int a[N][N];

int main()
{
    int n;
    cin >> n;

    for (int i = 1 ; i <= n ; i ++)
        for (int j = 1; j <= i ; j ++)
            scanf("%d", &a[i][j]);

    for (int i = n - 1 ; i >= 1; i --)
        for (int j = 1 ; j <= i ; j ++)
            a[i][j] += max(a[i + 1][j], a[i + 1][j + 1]);

    cout << a[1][1] << endl;

    return 0;
}

记忆化搜索

记忆化搜索是一种通过记录已经遍历过的状态的信息，从而避免对同一状态重复遍历的搜索实现方式。

因为记忆化搜索确保了每个状态只访问一次，它也是一种常见的动态规划实现方式。

例：
普通的 01 背包问题

使用一个二维数组记录计算过的状态

include <iostream>
include <cstring>
include <cmath>

using namespace std;
const int N = 1010, INF = 0x3f3f3f3f;
int c[N], w[N];
int mm[N][N];
int n, v;


int dfs(int pos, int left)
{
    if (mm[pos][left] != -1) return mm[pos][left];
    if (pos == n + 1) return mm[pos][left] = 0;

    int dfs1, dfs2 = -INF;
        dfs1 = dfs(pos + 1, left);
    if (left >=c[pos])
        dfs2 = dfs(pos + 1, left - c[pos]) + w[pos];

    return mm[pos][left] = max(dfs1, dfs2);

}

int main(){

    cin >> n >> v;

    memset(mm, -1, sizeof mm);

    for (int i = 1 ; i <= n ; i ++ )
        cin >> c[i] >> w[i];

    cout << dfs(1, v) << endl;


    return 0;
}

与递归的联系与区别：在形式上两者是高度类似的。这是由于他们使用了相同的状态表示方式和类似的状态转移。也正因为如此，一般来说两种实现的时间复杂度是一样的

洛谷 p1413open in new window

滑雪，可以使用记忆化的思路来考虑。

总结一下记忆化搜索的步骤：

记忆数组初始化（比如说求最大值就初始化为-1）
当搜索到某个状态时，若该状态已经更新过了，直接返回
若该状态还未更新，则和一般 dp 一样用状态转移方程更新

#include <bits/stdc++.h>

using namespace std;
const int N = 103;

int g[N][N];
int f[N][N];

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int n, m;
int res;

int dp(int x, int y)
{
    if (f[x][y] != -1) return f[x][y];

    int ma = 0;
    for (int i = 0 ; i < 4 ; i ++)
    {
        int a = x + dx[i], b = y + dy[i];

        if (a < 1 || a > n || b < 1 || b > m) continue;

        if (g[x][y] > g[a][b]) ma = max(ma , dp(a, b));
    }

    return f[x][y] = ma + 1;
}


int main()
{
    cin >> n >> m;

    memset(f, -1, sizeof f);

    for (int i = 1; i <= n ; i ++)
        for (int j = 1; j <= m ; j ++)
            scanf("%d", &g[i][j]);

    for (int i = 1; i <= n ; i ++)
        for (int j = 1; j <= m ; j ++)
            res = max(dp(i, j), res);

    cout << res << endl;

    return 0;
}

区间 DP

区间 dp 一般使用两维表示一段区间的端点的，需要注意的是使用递推时，会先枚举区间的长度再枚举左（或右端点），然后使用左端点+区间长度（右端点-区间长度）表示右（左）端点。

注意枚举区间长度时，由于范围问题，区间长度可能由 0 开始

洛谷 P1005 open in new window

include <bits/stdc++.h>
define LL __int128

using namespace std;
const int N = 83;
LL a[N][N];
LL f[N][N];
LL res;

int n, m;

inline LL
read()
{
    LL x = 0, f = 1;

    char ch = getchar();

    while (ch < '0' || ch > '9' )
    {
        if (ch == '-') f = -1;
        ch = getchar();
    }

    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }

    return x * f;
}

inline void
print(LL x)
{
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) print(x / 10);
    putchar(x % 10 + '0');
}

LL
dp(LL a[])
{
    memset(f, 0, sizeof f);

    for (int i = 0 ; i < m ; i ++)
        for (int j = 1 ; i + j <= m ; j ++)
            f[j][i+j] = max((f[j+1][i+j] + a[j]) << 1, (f[j][i+j-1]+a[i+j]) << 1);

    return f[1][m];
}

int
main()
{
    cin >> n >> m;

    for (int i = 1 ; i <= n ; i ++)
        for (int j = 1 ; j <= m ; j ++)
            a[i][j] = read();

    for (int i = 1 ; i <= n ; i ++) res += dp(a[i]);

    print(res);

    return 0;
}

这里的区间表示区间内最大值，那么根据题意一次只能从区间左右端点取值，因此由左端点+1 或右端点-1 转移过来

石子合并

设有 N 堆石子排成一排，其编号为 1,2,3,…,N 。

每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N 堆石子合并成为一堆。

每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。

找出一种合理的方法，使总的代价最小，输出最小代价。

f[l][r] 表示将区间 [l, r]和为一堆所需最小代价

#include <iostream>
using namespace std;
const int N = 310;

int s[N], f[N][N];
int n;

int main() {
    cin >> n;

    // 使用前缀和，计算区间的值， 否则 2.7 * E7 再多一点求和开销会超时
    for (int i = 1; i <= n; i ++) cin >> s[i], s[i] += s[i-1];

    // 枚举区间长度 不直接枚举 l r
    // 因为 计算f[l][r] 使用了 f[l][k] 与 f[k+1][r], 而 f[k+1][r] 在 f[l][r] 后才能计算
    // 如果枚举区间长度，f[l][k], f[k+1][r] 的长度比f[l][r] 短，会先计算出来
    for (int len = 2; len <= n; len ++)
        for (int l = 1; l + len - 1 <= n ; l ++) {
            int r = l + len - 1;
            // 初始化问题： 需要把f[x][x] 初始化为 0, 因为只操作一堆代价为0, 默认为0因此这里不用写
            // 除了 f[x][x] 以为的元素应该都初始化为 INF，方便直接取 min，len >= 2 因此 l != r，计算f[l][r] 前
            // 赋予为 INF 即可
            f[l][r] = 1e8;
            // k 的范围: k >= l && k+1 <= r --> l <= k <= r - 1
            for (int k = l; k <= r - 1 ; k ++)
                f[l][r] = min(f[l][r], f[l][k] + f[k+1][r] + s[r] - s[l-1]);
        }
    cout << f[1][n];

    return 0;
}

🎒 问题

01 背包

n 个物品， m 大小的背包

$0\leq n,m\leq 1000$

每种物品只有一个，只能选择放或不放。

求背包价值最大的决策

#include <bits/stdc++.h>

using namespace std;
const int N = 1e3 + 5;
int v[N], w[N];
int dp[N][N];

int n, m;

int main() {
    cin >> n >> m;

    for (int i = 1; i <= n; i ++) {
        int a, b;
        cin >> a >> b;
        v[i] = a, w[i] = b;
    }

    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++){
            dp[i][j] = dp[i-1][j];
            if (j >= v[i])
                dp[i][j] = max(dp[i][j], dp[i-1][j-v[i]] + w[i]);

        }

    cout << dp[n][m] << endl;

    return 0;
}

优化

#include <bits/stdc++.h>


using namespace std;
const int N = 1e3 +5;
int n, m;
int f[N];

int main() {

    cin >> n >> m;

    for (int i = 1; i <= n; i ++) { // 发现dp[i][x] 只与 dp[i-1][x] 有关，且我们从小到大迭代，可以省掉这维空间
        int v, w;
        cin >> v >> w;
        for (int j = m; j >= v; j --) // 当 j < v[i] 时，dp[i][j] = dp[i-1][j], 由于我们省掉了第一维空间，赋值操作都省了，仅当 j >= v[i] 时才需要决策
        // 🎒 背包空间从大到小递减，是因为决策大的背包空间时需要使用第一上维的dp[n-1][j-v[i]]，如果先决策小的背包体积，可能会把信息覆盖掉了（很大可能）
            f[j] = max(f[j], f[j-v] + w);
    }

完全背包

n 个物品， m 大小的背包

$0\leq n,m\leq 1000$

每种物品有无限个可以选择

求背包价值最大的决策

// 公式推导:
//    当 j >= v[i];
//        dp[i, j] = max(dp[i - 1, j], dp[i - 1, j - v[i]] + w[i],
//            dp[i - 1, j - v[i] * 2] + w[i] * 2， ...  ,dp[i - 1, j - v[i] * k] + w[i] * k);
//    变化：j = j - v[i]
//        dp[i, j - v[i]] = max(dp[i - 1, j - v[i]], dp[i - 1, j - v[i] * 2] + w[i]，dp[i - 1, j - v[i] * 3] + w[i] * 2,  //            dp[i - 1, j - v[i] * 3] + w[i] * 2, dp[i - 1, j - v[i] * (k + 1)] + w[i] * k );
//    替换：
//    dp[i, j] = max(dp[i - 1, j], dp[i, j - v[i] + w[i]);

#include <bits/stdc++.h>

using namespace std;
const int N = 1e3 + 5;
int v[N], w[N];
int f[N][N];
int n, m;

int main (){
    cin >> n >> m;

    for (int i = 1; i <= n; i ++) {
        cin >> v[i] >> w[i];
    }

    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m ; j ++){
            f[i][j] = f[i-1][j];
            if (j >= v[i]) f[i][j] = max(f[i][j], f[i][j-v[i]]+w[i]);
        }
    cout << f[n][m] << endl;

    return 0;
}

优化

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;
int v[N], w[N];
int f[N];
int n, m;

int main (){
    cin >> n >> m;

    for (int i = 1; i <= n; i ++) {
        int v, w;
        cin >> v >> w;
        for (int j = v; j <= m ; j ++) // 从 v 开始递增，因为 dp[i][j] = max(dp[i-1][j], dp[i][j-v] + w); dp[i][j] 不与
            // dp[i-1][j-x] 有关，不用考虑覆盖问题。
            f[j] = max(f[j], f[j-v]+w);
    }

    cout << f[m] << endl;

    return 0;
}

多重背包 I

n 个物品， m 大小的背包

每种物品有限个s可以选择

求背包价值最大的决策

数据量不大的情况可以直接暴力 $O(n^3)$

$0\leq n, m\leq 100$

#include <iostream>

using namespace std;
const int N = 110;
int v[N], w[N], s[N];
int f[N][N];
int n, m;

int main (){
    cin >> n >> m;

    for (int i = 1;  i <= n; i ++) {
        int v, w, s;
        cin >> v >> w >> s;
        for (int j = 1; j <= m; j ++)
            for (int k = 0; k <= s && k * v <= j; k ++){
                // 无法优化一维，如果只用 一维 f[j] 上一个物品的信息和k-1的信息可能会重叠
                f[i][j] = max(f[i][j], f[i-1][j - v * k] + w * k);
            }
    }
    cout << f[n][m] << endl;
    return 0;
}

多重背包 II

物品的数据量大的情况下

$0 \leq n \leq 1000,0\leq m\leq 2000$

可以把同一种物品的拆成若干组，并把一组和为新的物品，那么可以把问题转换为 01 背包问题

这样拆的前提是: 拆解以后决策的结果是不能改变的，就是说拆成若干组，必须能使用每组的数量组合为原来的数量

为了使得时间复杂度尽量少，因此拆解成的组数也应该尽量少——二进制拆法

$2^0+2^2+2^3+...+2^k+b=x$

#include <bits/stdc++.h>

using namespace std;
const int N = 11003, M = 2003;
int v[N], w[N];
int f[M];
int cnt;
int n, m;

int main() {
    cin >> n >> m;

    for (int i = 1; i <= n; i ++) {
        int a, b, c;
        cin >> a >> b >> c;
        for (int k = 1; k <= c; c -= k, k *= 2) // 二进制拆法
            v[++ cnt] = a * k, w[cnt] = b * k;
        if (c) v[++ cnt] = a * c, w[cnt] = b * c;
    }

    for (int i = 1; i <= cnt; i ++) // 01
        for (int j = m; j >= v[i]; j --)
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[m] << endl;

    return 0;
}

分组背包

n 组物品， m 大小的背包

$0\le n,m \leq 100$

每组物品只能选一个

#include <iostream>

using namespace std;
const int N = 110;
int v[N][N], w[N][N], s[N], f[N];

int n, m;

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) {
        cin >> s[i];
        for (int j = 1; j <= s[i] ; j ++)
            cin >> v[i][j] >> w[i][j];
    }
    for (int i = 1; i <= n ; i ++ )
        for (int j = m; j >=0 ; j --)
            for (int k = 1; k <= s[i]; k ++)
                if (j >= v[i][k])
                    f[j] = max(f[j], f[j-v[i][k]] + w[i][k]);

    cout << f[m];

    return 0;
}

线性 DP

数字三角形

从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。

基于上一步的决策，决策该位置

可以从顶部往下决策，但是需要注意某点的上面两步可能不在范围内，因此需要初始化，把空的位置设为绝对的小值

决策结束后，需要从最底边选出最大的值作为答案

#include <bits/stdc++.h>
using namespace std;
const int N = 510, INF = 1e9;
int f[N][N];
int n;

int main() {
    cin >> n;
    for (int i = 0; i <= n; i ++)
        for (int j = 0; j <= n; j ++)
            f[i][j] = -INF;

    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= i; j ++)
            cin >> f[i][j];

    f[1][1];
    for (int i = 2; i <= n; i ++)
        for (int j = 1; j <= i; j ++)
            f[i][j] += max(f[i-1][j], f[i-1][j-1]);

    int res = -INF;
    for (int i = 1; i <= n ; i ++)
        res = max(res, f[n][i]);

    cout << res << endl;
    return 0;
}

可以从底部出发，那么上一步一定在范围内了，而最后只能走到顶点

#include <bits/stdc++.h>
using namespace std;
const int N = 510;
int f[N][N];
int n;

int main() {
    cin >> n;

    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= i; j ++)
            cin >> f[i][j];

    for (int i = n; i >= 1; i --)
        for (int j = 1; j <= i; j ++)
            f[i][j] += max(f[i+1][j], f[i+1][j+1]);

    cout << f[1][1];

    return 0;
}

最长上升子序列 I

给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。

子序列在原数列中不一定是连续的

如果数据量不大，可以每个字符遍历一遍之前的字符，找到上一个插入合法且长度最大的子序列，则上次+1 得到本次的最大长度

$1\le N \le 1000$

$O(n^2)$

f[i] 表示以a[i]为结尾的最长子序列长度

#include <iostream>

using namespace std;
const int N = 1e3 + 3;
int a[N], f[N];
int n;

int main () {
    cin >> n;
    for (int i = 1; i <= n; i ++)
        cin >> a[i];

    for (int i = 1; i <= n; i ++) {
        f[i] = 1;   // 如果没有能以该数字结尾的上升子序列，就自起一个
        for (int j = 1; j < i; j ++) {
            if (a[i] > a[j]) f[i] = max(f[j] + 1, f[i]);
        }
    }

    int res = 0;
    for (int i = 1; i <= n; i ++)
        res = max(res, f[i]);

    cout << res;

    return 0;
}

最长上升子序列 II

如果数据量比较大了，需要进行优化

$1\le N\le 100000$

维护一个队列q[x] ，值的含义是长度为x上升子序列中，结尾最小的数字

那么该队列内的值必然是递增的，且长度就是原数组中最长上升子序列的长度

todo 证明

$O(nlogn)$

#include <iostream>

using namespace std;

const int N = 1e5 + 5;
int q[N];
int len;

int main (){
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        int x;
        cin >> x;
        int l = 0, r = len;
        while (l < r) {
            int mid = l + r + 1>> 1;
            if (q[mid] < x) l = mid;
            else r = mid - 1;
        }
        len = max(len, l + 1);
        q[l + 1] = x;
    }

    cout << len;

    return 0;
}

最长公共子序列

给定两个长度分别为 N 和 M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。

f[i][j] 的含义是 A[1~i] 与 B[1~j] 的最长公共子序列长度

分为 4 种情况:

不选A[i]，不选B[j]
选B[j]，不选A[i]
选A[i]，不选B[j]
选A[i]，选B[j]

f[i-1][j] 包含不选A[i] and (不选 B[j] or 选B[j]) 的请求，同理f[i-1][j]也是，但是没关系，取最大值时范围重叠没有影响

#include <bits/stdc++.h>

using namespace std;
const int N = 1003;
int f[N][N];
char a[N], b[N];
int n, m;

int main() {
    cin >> n >> m;
    scanf("%s%s", a + 1, b + 1);

    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++) {
            f[i][j] = max(f[i-1][j], f[i][j-1]);
            if (a[i] == b[j]) f[i][j] = max(f[i][j], f[i-1][j-1] + 1);
        }

    cout << f[n][m];

    return 0;
}

最短编辑距离

给定两个字符串 A 和 B，现在要将 A 经过若干操作变为 B

可进行的操作有：

删除–将字符串 A 中的某个字符删除。
插入–在字符串 A 的某个位置插入某个字符。
替换–将字符串 A 中的某个字符替换为另一个字符。

现在请你求出，将 A 变为 B 至少需要进行多少次操作。

f[i][j] 表示 A 前 i 字符和 B 前 j 个字符匹配需要的最小操作数

决策可以分为四种情况:

A 前i-1 与 B 前j-1字符相等，且A[i] = B[j] 本轮不需操作
A 前i-1 与 B 前j-1字符相等，且A[i] != B[j] 本轮替换A[i]代价最小
A 前i 与 B 前j-1字符相等，本轮增加A[i+1] = B[j]代价最小
A 前i-1 与 B 前j字符相等，本轮删除A[i]代价最小

#include <iostream>

using namespace std;
const int N = 1003;
int n, m;
char a[N], b[N];
int f[N][N];

int main() {
    cin >> n >> a + 1;
    cin >> m >> b + 1;

    for (int i = 0; i <= m ; i ++) f[0][i] = i;
    for (int i = 0; i <= n; i ++) f[i][0] = i;

    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
            f[i][j] = min(f[i-1][j], f[i][j-1]) + 1,
            f[i][j] = min(f[i][j], f[i-1][j-1] + (a[i] != b[j]));

    cout << f[n][m];
    return 0;
}

编辑距离

899. 编辑距离open in new window

题意和上题差不多

#include <bits/stdc++.h>

using namespace std;
const int N = 1e3 + 3;
char str[N][N];
int f[N][N];
int n, m;

int getDist(char *a, char *b) {
    int la = strlen(a + 1), lb = strlen(b + 1);
    for (int i = 0; i <= la; i ++) f[i][0] = i;
    for (int i = 0 ; i <= lb ; i ++) f[0][i] = i;

    for (int i = 1; i <= la; i ++)
        for (int j = 1; j <= lb ; j ++)
            f[i][j] = min(f[i-1][j], f[i][j-1]) +1,
            f[i][j] = min(f[i][j], f[i-1][j-1] + (a[i] != b[j]));

    return f[la][lb];
}

int main() {

    cin >> n >> m;

    for (int i = 0; i < n ; i ++)
        cin >> str[i] + 1;


    while(m --) {
        int limit;
        char q[N];
        int res = 0;
        cin >> q + 1 >> limit;
        for (int j = 0; j < n; j ++)
            if (getDist(q, str[j]) <= limit) res ++;
        cout << res << endl ;
    }

    return 0;
}

计数类 DP

整数划分

一个正整数 n 可以表示成若干个正整数之和，形如：n=n_1+n_2+…+n_k，其中 n_1≥n_2≥…≥n_k,k≥1。

$1\le n\le 1000$

f[i][j] 表示把数 i 分为 j 个数，的方案数

#include <iostream>

using namespace std;
const int N = 1e3 + 3, MOD = 1e9 + 7;
int n, f[N][N];

int main () {
cin >> n;
f[0][0] = 1;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= i; j ++)
// 表示 最小值为 1 和 最小值大于 1 的两种情况
f[i][j] = (f[i-1][j-1] + f[i-j][j]) % MOD;

    int res = 0;
    for (int i = 1; i <= n ; i ++) res = (res + f[n][i]) % MOD;
    cout << res <<endl;
    return 0;

}

完全背包解法

f[i][j] 表示从 1~i 中选总和等于为 j 的方案数

#include <iostream>

using namespace std;
const int N = 1e3 + 3, MOD = 1e9 + 7;
int n, f[N][N];

int main () {
cin >> n;

    for (int i = 1; i <= n ; i ++) {
        f[i][0] = 1;
        for (int j = 1; j <= n; j ++) {
            f[i][j] = f[i-1][j];
            if (j >= i) f[i][j] = (f[i][j] + f[i][j-i]) % MOD;
        }
    }
    cout << f[n][n];
    return 0;
}

优化

#include <iostream>

using namespace std;
const int N = 1e3 + 3, MOD = 1e9 + 7;
int n, f[N];

int main () {
cin >> n;

    f[0]= 1;
    for (int i = 1; i <= n ; i ++) {
        for (int j = i; j <= n; j ++) {
            f[j] = (f[j] + f[j-i]) % MOD;
        }
    }
    cout << f[n];
    return 0;
}

# 动态规划

# 记忆化搜索

# 区间 DP

# 石子合并

# 🎒 问题

# 01 背包

# 完全背包

# 多重背包 I

# 多重背包 II

# 分组背包

# 线性 DP

# 数字三角形

# 最长上升子序列 I

# 最长上升子序列 II

# 最长公共子序列

# 最短编辑距离

# 编辑距离

# 计数类 DP

# 整数划分

动态规划

记忆化搜索

区间 DP

石子合并

🎒 问题

01 背包

完全背包

多重背包 I

多重背包 II

分组背包

线性 DP

数字三角形

最长上升子序列 I

最长上升子序列 II

最长公共子序列

最短编辑距离

编辑距离

计数类 DP

整数划分