当前位置： 首页 > news >正文

动态规划

news 2025/8/13 11:14:36

经典线性 DP 问题

1. 背包问题

背包九讲——全篇详细理解与代码实现-CSDN博客
背包 DP - OI Wiki (oi-wiki.org)

0/1 背包

n 个物品，每个物品有一个价值 w[i] 和一个重量 v[i] 。背包的最大承重为 m。每个物品只能使用一次（0/1 意味着要么不选这个物品，要么完全选这个物品）

int w[N], v[N]; // 价值、重量
int dp[N][N];int solve(int n, int V) // n件物品、V总体积
{for (int i = 1; i <= n; i++)for (int j = 0; j <= V; j++)if (j < v[i])dp[i][j] = dp[i - 1][j];elsedp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);return dp[n][V];
}
int w[N], v[N]; // 价值、重量
int dp[N];int solve(int n, int V) // n件物品、V总重量
{for (int i = 1; i <= n; i++)for (int j = V; j >= v[i]; j--)dp[j] = max(dp[j], dp[j - v[i]] + w[i]);return dp[V];
}
int w[N], v[N]; // 价值、重量
int dp[N];int solve()
{for (int i = 1; i <= n; i++) cin >> w[i] >> v[i], s[i] = s[i - 1] + v[i];for (int i = 1; i <= n; i++) {int bound = max(v[i], V - (s[n] - s[i]));for (int j = V; j >= bound; j--)dp[j] = max(dp[j], dp[j - v[i]] + w[i]);}return dp[V];
}

  • 要求恰好装满背包，那么在初始化时除了 dp[0] 为 0，其它 dp[1...V] 均设为 − ∞ ，这样就可以保证最终得到的 dp[N] 是一种恰好装满背包的最优解其实 dp[ 1...j...N] 分别对应着恰好装满容量为 j 的背包的最优解）

  • 没有要求必须把背包装满，而是只希望所装物品价值尽量大，初始化时应该将 dp[0...V] 全部设为 0（此时 dp[j] 则表示不必装满容量为 j 的背包的最优解）

分组背包

假设有 n 组物品，每组物品的数量为 s[i]，但在同一组内的物品冲突，因此每组最多只能选择一件物品，每组的物品有自己的重量 v[i][j] 和价值 w[i][j]。我们需要从这些物品中选择一些放入背包中，使得背包中物品的总价值最大，同时不超过背包的最大承重 m。

分组背包问题就是在 0/1背包问题 的基础之上，多了一个在每个组中选出最优的那个物品（或者不选） 。

中层循环是从背包容量 m 到 0 的逆序遍历，这是为了防止同一个组中的物品被重复放入背包（即保证每组中至多选择一个物品）

int w[N][N], v[N][N], s[N];	// w价值、v重量
int dp[N];
int n, m;int solve(int n, int m) //n组物品、m总容量、每组物品s[i]个
{for (int i = 1; i <= n; i++){for (int j = m; j >= 0; j--){for (int k = 1; k <= s[i]; k++) // 遍历第i组中的每个物品{if (j >= v[i][k])dp[j] = max(dp[j], dp[j - v[i][k]] + w[i][k]);}}}return dp[m];
}

for (int i = 1; i <= n; i++) 
{cin >> s; // 第i组的物品数量for (int j = 1; j <= s; j++) cin >> c[j] >> w[j]; //组中每个物品的属性for (int j = V; j >= 0; j--)for (int k = 1; k <= s; k++)if (j >= c[k])f[j] = max(f[j], f[j - c[k]] + w[k]);// 由于每组物品只能选一个，所以可以覆盖之前组内物品最优解的来取最大值
}

完全背包

完全背包问题是背包问题的一种变体。与 0/1背包问题 不同的是，在完全背包问题中，每种物品都有无限多个可用，这意味着可以选择任意数量的同一种物品，只要不超过背包的容量限制

  • 朴素写法
int w[N], v[N]; // w价值、v重量
int dp[N][N];int solve(int n, int V) //n组物品、V总容量
{for (int i = 1; i <= n; i++)for (int j = 0; j <= V; j++)for (int k = 0; k * v[i] <= j; k++)dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i] * k] + w[i] * k);return dp[n][V];
}
  • 优化一
int w[N], v[N]; // w价值、v重量
int dp[N][N];int solve(int n, int V) // n组物品、V总容量
{for (int i = 1; i <= n; i++){for (int j = 0; j <= V; j++){if (j < v[i])dp[i][j] = dp[i - 1][j];elsedp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]);}}return dp[n][V];
}
  • 优化二
int w[N], v[N]; // w价值、v重量
int dp[N];int solve(int n, int V) // n组物品、V总容量
{for (int i = 1; i <= n; i++)for (int j = v[i]; j <= V; j++)dp[j] = max(dp[j], dp[j - v[i]] + w[i]);return dp[V];
}

多重背包

多重背包问题（也称为有数量限制的背包问题）是背包问题的一个变种。在这种情况下，每种物品都有一个数量限制，即每种物品最多可以选取多少个。这介于 0/1背包问题（每种物品只能选一次）和 完全背包问题（每种物品可以无限次选取）之间。

  • 问题定义

有 n 组物品，每组物品有 s[i] 个，每种物品的重量为 v[i]、价值为 w[i]。需要从这些物品中选择一些放入背包中，使得背包中物品的总价值最大，同时不超过背包的最大承重 m。

    1. 直接展开法

这种方法直接将每种物品的所有可能性展开，例如，如果某种物品的数量上限是 5，则可以构造出 5 个虚拟物品（0 个、1 个、2 个、3 个、4 个和 5 个），然后将问题转化为 0/1 背包问题。

    1. 平滑化处理

这种方法通过对物品进行预处理，减少状态转移次数，从而提高效率。具体来说，可以将数量限制较大的物品进行平滑化处理，将其转换为几个子问题。

平滑化处理的步骤:

  1. 预处理阶段：对于每种物品，如果数量上限较大，可以将其分解成多个子物品。
  2. 状态转移：利用预处理后的物品进行动态规划的状态转移。
  • 一般方法
int w[N], v[N], s[N]; // w价值、v重量
int dp[N][N];int solve(int n, int V) // n组物品、V总容量
{for (int i = 1; i <= n; i++){for (int j = 0; j <= V; j++){for (int k = 0; k <= s[i] && k * v[i] <= j; k++){dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i] * k] + w[i] * k);}}}return dp[n][V];
}
  • 滚动数组
int w[N], v[N], s[N]; // w价值、v重量
int dp[N];int solve(int n, int V) // n组物品、V总容量
{for (int i = 1; i <= n; i++){for (int j = m; j >=v[i]; j--){for (int k = 0; k <= s[i] && k * v[i] <= j; k++){dp[j] = max(dp[j], dp[j - v[i] * k] + w[i] * k);}}}return dp[V];
}
  • 二进制分组优化
    将第 i 种物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为 1 , 2 , 4 , . . . , \(2^k\) − 1, s[i] − \(2^k\) + 1 ，且 k 是满足 s[i] − \(2^k\) + 1 > 0 的最大整数。

例如，如果 s[i] 为 13 ，就将这种物品分成系数分别为 1 , 2 , 4 , 6 的四件物品，此时 k = 3 。分成的这几件物品的系数和为 s[i] ，其中的 6 是为了保证不可能取多于 s[i] 件的第 i 种物品。

int w[N], v[N], s[N]; // w价值、v重量、s数量
int dp[N];int solve(int n, int V)			// n组物品、V总容量
{for (int i = 1; i <= n; i++) {int num = min(s[i], V / v[i]); // V/c[i]是最多能放多少个进去，优化上界for (int k = 1; num > 0; k <<= 1) {if (k > num) k = num;num -= k;for (int j = V; j >= v[i] * k; j--) // 01背包dp[j] = max(dp[j], dp[j - v[i] * k] + w[i] * k);}}return dp[V];
}
  • 单调队列优化

#include <bits/stdc++.h>
constexpr int MAXV = 4e4 + 10;
constexpr int MAXN = 1e2 + 10;
using namespace std;int n, W, last = 0, now = 1;
array<int, MAXN> v, w, k;
array<array<int, MAXV>, 2> f;
deque<int> q;int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> W;
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i] >> k[i];    for (int i = 1; i <= n; i++)
    {
        for (int y = 0; y < w[i]; y++)
        {
            // 清空队列
            deque<int>().swap(q);            for (int x = 0; x * w[i] + y <= W; x++)
            {
                // 弹出不在范围的元素
                while (!q.empty() && q.front() < x - k[i])
                    q.pop_front();                // 保证队列单调
                while (!q.empty() && f[last][q.back() * w[i] + y] - q.back() * v[i] < f[last][x * w[i] + y] - x * v[i])q.pop_back();                q.push_back(x);
                
                f[now][x * w[i] + y] = f[last][q.front() * w[i] + y] - q.front() * v[i] + x * v[i];
            }
        }
        swap(last, now);
    }
    cout << f[last][W] << endl;
    return 0;
}
//p：某类物品数量，w：某类物品花费，v：某类物品价值，V:商品总价值
void MultiPack(int p, int w, int v) {for (int j = 0; j < w; j++) { //j为w的所有组int head = 1, tail = 0;for (int k = j, i = 0; k <= V / 2; k += w, i++) {int r = f[k] - i * v;while (head <= tail and r >= q[tail].v) tail--;q[++tail] = node(i, r);while (q[head].id < i - p) head++; //需要的物品数目f[k] = q[head].v + i * v;}}
}

混合背包

将 0/1背包 、完全背包、多重背包 混合起来，也就是说，有的物品只可以取一次（01 背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包）

for (int i = 1; i <= n; i++) 
{cin >> c >> w >> p;if (p == 0) //完全背包for (int j = c; j <= V; j++)f[j] = max(f[j], f[j - c] + w);else if (p == -1) //01背包for (int j = V; j >= c; j--)f[j] = max(f[j], f[j - c] + w);else { //多重背包二进制优化int num = min(p, V / c);for (int k = 1; num > 0; k <<= 1) {if (k > num) k = num;num -= k;for (int j = V; j >= c * k; j--)f[j] = max(f[j], f[j - c * k] + w * k);}}
}

二维费用背包

对于每件物品，具有两种不同的费用：选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。设第 i 件物品所需的两种代价分别为 c[i] 和 g[i] 。两种代价可付出的最大值（两种背包容量）分别为 V 和 M 。物品的价值为 w[i]。

与 0/1背包 不同的是选一个物品会消耗两种价值，只需在状态中增加一维存放第二种价值即可


for (int i = 1; i <= n; i++)for (int j = V; j >= c[i]; j--)for (int k = M; k >= g[i]; k--)f[j][k] = max(f[j][k], f[j - c[i]][k - g[i]] + w[i]);

有依赖的背包问题

这种背包问题的物品间存在某种“依赖”的关系。也就是说，i 依赖于 j，表示若选物品 i，则必须选物品 j。

考虑分类讨论。对于一个主件和它的若干附件，有以下几种可能：只买主件，买主件 + 某些附件。因为这几种可能性只能选一种，所以可以将这看成分组背包。

如果是多叉树的集合，则要先算子节点的集合，最后算父节点的集合。

泛化物品的背包

这种背包，没有固定的费用和价值，它的价值是随着分配给它的费用而定。在背包容量为 V 的背包问题中，当分配给它的费用为 v[i] 时，能得到的价值就是 h(v[i])。这时，将固定的价值换成函数的引用即可。

杂项

小优化

根据贪心原理，当费用相同时，只需保留价值最高的；当价值一定时，只需保留费用最低的；当有两件物品 i，j 且 i 的价值大于 j 的价值并且 i 的费用小于 j 的费用时，只需保留 i 。

背包问题变种

输出方案

输出方案其实就是记录下来背包中的某一个状态是怎么推出来的。我们可以用 g[i][v] 表示第 i 件物品占用空间为 v 的时候是否选择了此物品。然后在转移时记录是选用了哪一种策略（选或不选）。输出时的伪代码：

int v = V; // 记录当前的存储空间// 因为最后一件物品存储的是最终状态，所以从最后一件物品进行循环
for (从最后一件循环至第一件)
{
    if (g[i][v])
    {
        选了第 i 项物品;
        v -= 第 i 项物品的重量;
    }
    else
    {
        未选第 i 项物品;
    }
}
求方案数
求最优方案总数
背包的第 k 优解

2. 最长公共子序列（LCS）

f[i][j] 表示只考虑 A 的前 i 个元素，B 的前 j 个元素时的 最长公共子序列 的长度

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

3. 最长递增子序列（LIS）

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

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1), f(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
        
    int ans = -1;
    for (int i = 1; i <= n; i++)
    {
        f[i] = 1;
        for (int j = 1; j < i; j++)
            if (a[j] < a[i])	//最长不下降子序列 改为: a[j] <= a[i]
                f[i] = max(f[i], f[j] + 1);
        ans = max(ans, f[i]);
    }
    
    cout << ans << endl;
}

//最长不下降子序列
for (int i = 0; i < n; ++i) scanf("%d", a + i); memset(dp, 0x1f, sizeof dp); mx = dp[0]; for (int i = 0; i < n; ++i) *upper_bound(dp, dp + n, a[i]) = a[i];ans = 0; while (dp[ans] != mx) ++ans;

4. 最长公共上升子序列（LCIS）

272. 最长公共上升子序列 - AcWing题库
AcWing 272. 最长公共上升子序列 - AcWing

const int N = 3010;
int n;
int a[N], b[N], f[N][N];
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)	cin >> a[i];
    for (int i = 1; i <= n; i++)	cin >> b[i];    for (int i = 1; i <= n; i++)
    {
        int maxv = 1;
        for (int j = 1; j <= n; j++)
        {
            f[i][j] = f[i - 1][j];
            if (a[i] == b[j])	f[i][j] = max(maxv, f[i][j]);
            if (a[i] > b[j])	maxv = max(maxv, f[i - 1][j] + 1);
        }
    }    int res = 0;
    for (int i = 1; i <= n; i++)	res = max(res, f[n][i]);
    
    cout << res << endl;
}

5. 最短公共超序列

最短公共超序列（Shortest Common Supersequence，简称 SCS）是指在不改变两个给定序列中字符出现顺序的前提下，通过在这些序列中插入尽可能少的其他字符，使得这两个序列都成为结果序列的子序列

给定两个字符串 \(str1\) 和 \(str2\) ，我们可以构建一个二维数组 \(dp[][]\) ，其中 \(dp[i][j]\) 表示 \(str1\) 的前 \(i\) 个字符和 \(str2\) 的前 \(j\) 个字符的最短公共超序列的长度。动态规划的递推公式如下：

  • 当 \(str1[i]\) 等于 \(str2[j]\) 时，\(dp[i][j] = dp[i-1][j-1] + 1\)；
  • 当 \(str1[i]\) 不等于 \(str2[j]\) 时，\(dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1\) 。
const int N = 105;
int dp[N][N];
char str1[N], str2[N], scs[N];int main() 
{scanf("%s", str1);scanf("%s", str2);int len1 = strlen(str1), len2 = strlen(str2);for (int i = 0; i <= len1; i++) dp[i][0] = i;for (int j = 0; j <= len2; j++) dp[0][j] = j;for (int i = 1; i <= len1; i++){for (int j = 1; j <= len2; j++) {if (str1[i - 1] == str2[j - 1])dp[i][j] = dp[i - 1][j - 1] + 1;elsedp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;}}// 构建最短公共超序列int index = dp[len1][len2];scs[index] = '\0';int i = len1, j = len2;while (i > 0 && j > 0) {if (str1[i - 1] == str2[j - 1]) {scs[--index] = str1[i - 1];i--; j--;}else if (dp[i - 1][j] < dp[i][j - 1]) scs[--index] = str1[--i];else scs[--index] = str2[--j];}while (i > 0) scs[--index] = str1[--i];while (j > 0) scs[--index] = str2[--j];printf("%s\n", scs);
}

6. 矩阵最长递增路径

方法一 DFS

  • 思路
    dfs: 以（x， y）为起点进行递归：
    ​ 对于每个（x, y）来说，遍历它上下左右四个坐标，查看是否越界或者满足递增的要求；
    ​ 若是满足要求就继续递归满足要求的点
    solve: 两重循环遍历矩阵中所有的点

  • 代码

void dfs(vector<vector<int>>& matrix, vector<vector<int>>& st, int count, int x, int y, int& res)
{array<int, 4> dx = {-1, 0, 1, 0};array<int, 4> dy = {0, 1, 0, -1};int n = st.size();int m = st[0].size();for(int i = 0; i < 4; ++i){int X = x + dx[i], Y = y + dy[i];if(X < 0 || X >= n || Y < 0 || Y >= m)continue;if(st[X][Y] == 0 && matrix[X][Y] > matrix[x][y]){st[X][Y] = 1;dfs(matrix, st, count + 1, X, Y, res);st[X][Y] = 0;}}res = max(res, count);
}int solve(vector<vector<int> >& matrix) 
{   int n = matrix.size();int m = matrix[0].size();int res = 1;vector<vector<int>> st(n, vector<int>(m));for(int i = 0; i < n; ++i)for(int j = 0; j < m; ++j)dfs(matrix, st, 1, i, j, res);return res;
}

方法二 ：优化—一个位置只递归一次

  • 思路
  1. 动态规划缓存: dp 矩阵用来缓存已经计算过的路径长度，避免重复计算。
  2. 减少递归调用: 通过在每个位置初始化时只调用一次 DFS，减少了不必要的递归调用。
  3. 简化函数参数: 去掉了 st 矩阵和 count 参数，将 dp 矩阵用作缓存，count 的功能由 dp[x][y] 代替。
  • 代码
class Solution {
public:void dfs(const vector<vector<int>>& matrix, vector<vector<int>>& dp, int x, int y, int& res) {array<int, 4> dx = {-1, 0, 1, 0};array<int, 4> dy = {0, 1, 0, -1};int n = matrix.size();int m = matrix[0].size();for (int i = 0; i < 4; ++i) {int X = x + dx[i], Y = y + dy[i];if (X < 0 || X >= n || Y < 0 || Y >= m || matrix[X][Y] <= matrix[x][y]) {continue;}if (dp[X][Y] == 0) {dfs(matrix, dp, X, Y, res);}dp[x][y] = max(dp[x][y], 1 + dp[X][Y]);}res = max(res, dp[x][y]);}int solve(vector<vector<int>>& matrix) {int n = matrix.size();if (n == 0) return 0;int m = matrix[0].size();vector<vector<int>> dp(n, vector<int>(m, 0));int res = 1;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if (dp[i][j] == 0) {dp[i][j] = 1;dfs(matrix, dp, i, j, res);}}}return res;}
};

7. 照相排列

271. 杨老师的照相排列 - AcWing题库

void solve()
{
    int n;
    while (cin >> n, n)
    {
        int s[5] = {0};
        for (int i = 0; i < n; i++)		cin >> s[i];
        int f[s[0] + 1][s[1] + 1][s[2] + 1][s[3] + 1][s[4] + 1];
        memset(f, 0, sizeof f);
        f[0][0][0][0][0] = 1;        for (int a = 0; a <= s[0]; a++)
            for (int b = 0; b <= min(a, s[1]); b++)
                for (int c = 0; c <= min(b, s[2]); c++)
                    for (int d = 0; d <= min(c, s[3]); d++)
                        for (int e = 0; e <= min(d, s[4]); e++)
                        {
                            int &x = f[a][b][c][d][e];
                            if (a && a - 1 >= b)	x += f[a - 1][b][c][d][e];
                            if (b && b - 1 >= c)	x += f[a][b - 1][c][d][e];
                            if (c && c - 1 >= d)	x += f[a][b][c - 1][d][e];
                            if (d && d - 1 >= e)	x += f[a][b][c][d - 1][e];
                            if (e)		x += f[a][b][c][d][e - 1];
                        }
        cout << f[s[0]][s[1]][s[2]][s[3]][s[4]] << endl;
    }
}

8. 编辑距离

编辑距离，是指两个字符串之间，由一个转成另一个所需的最少编辑操作次数

编辑操作包括 插入、删除 和 替换 字符

dp[i][j] 表示从 word1 的前 i 个字符转换到 word2 的前 j 个字符所需要的操作步骤

int solve(int n, int m)
{
    for (int i = 1; i <= n; i++)
        dp[i][0] = i;
    for (int i = 1; i <= m; i++)
        dp[0][i] = i;    for (int i = 1; i <= n;i++)
        for (int j = 1; j <= m;j++)
            if(a[i] == b[j])
                dp[i][j] = dp[i - 1][j - 1];
            else
                dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;    return dp[n][m];
}

9. 子集和问题

给定一个非负整数的集合 \(S\) ，一个值 \(M\) ，问 \(S\) 中是否有一个子集，其子集和等于 \(M\) 。

当 \(dp[i][j]=1\) 时，表示 \(S\) 的前 \(i\) 个元素存在一个子集和等于 \(j\) ，问题的答案是 \(dp[n][m]\)

用 \(a[1]\sim a[n]\) 记录集合 \(S\) 中的 \(n\) 个元素

  1. 若 \(a[i]>j\) ，则 \(a[i]\) 不能放在子集中，有 \(dp[i][j]=dp[i-1][j]\)
  2. 若 \(a[i]<=j\)，有两种选择；不把 \(a[i]\) 放在子集中，则 \(dp[i][j]=dp[i-1][j]\) ；把 \(a[i]\) 放在子集中，则 \(dp[i][j]=dp[i-1][j-a[i]]\)
int dp[N][N];
int a[N];
int n, m;
int main() 
{cin >> n >> m;for (int i = 1; i <= n; i++)cin >> a[i];for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {dp[i][j] = (i == 1 ? 0 : dp[i - 1][j]);if (j >= a[i])dp[i][j] = max(dp[i][j], dp[i - 1][j - a[i]] + a[i]);}}for (int i = n; i > 0; i--) //从最后一位往前获取{for(int j = 0; j <= m; j++){if (dp[i][m] - a[i] == dp[i - 1][j]) {cout << a[i] << " ";m = j;}}}return 0;
}

10. 最小划分

问题描述：给出一个正整数数组，把它分成 \(S_1\) 和 \(S_2\) 两部分，使 \(S_1\) 的数字和与 \(S_2\) 的数字和的 差的绝对值 最小

求出数组的和 sum ，转换为 0/1背包：背包的容量为 sum/2 ，把数组中的每个数字看作物品的体积，求出背包最多可以放 res 体积的物品，返回结果 |res-(sum-res)|

11. 行走问题

定义行走问题的状态 dp[i] 为走到第 i 步的走法数量，那么

dp[0] = 1, dp[1] = 1, dp[2] = 2
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3], i > 2

12. 最优游戏策略

数位统计 DP

P2602 [ZJOI 2010] 数字计数 - 洛谷 | 计算机科学教育新生态 (luogu. com. cn)

给定两个正整数 a 和 b，求在 [a, b] 中的所有整数中，每个数码 (digit) 各出现了多少次?

#define int long long
const int N = 15;int ten[N], dp[N];
int cnt1[N], cnt2[N]; // cnt[i]，统计数字 i 出现了多少次
int num[N];void init() // 预计算 dp[i]
{
    ten[0] = 1; // ten[i]：10 的 i 次方
    for (int i = 1; i <= N; i++)
    {
        dp[i] = i * ten[i - 1]; // 或者 dp[i] = dp[i - 1] * 10 +ten[i - 1];
        ten[i] = 10 * ten[i - 1];
    }
}void solve(int x, int *cnt)
{
    int len = 0; // 数字 x 有多少位
    while (x)    // 分解 x ，num[i] 为 x 的第 i 位数字
    {
        num[++len] = x % 10;
        x /= 10;
    }
    for (int i = len; i >= 1; i--) // 从高到低处理 x 的每位
    {
        for (int j = 0; j <= 9; j++)
            cnt[j] += dp[i - 1] * num[i]; // 普通情况
        for (int j = 0; j < num[i]; j++)
            cnt[j] += ten[i - 1]; // 特判最高位比num[i]小的数字
        int num2 = 0;
        for (int j = i - 1; j >= 1; j--)
            num2 = num2 * 10 + num[j];
        cnt[num[i]] += num2 + 1; // 特判最高位的数字 num[i]
        cnt[0] -= ten[i - 1];    // 特判前导 0
    }
}signed main()
{
    init();
    int a, b;
    cin >> a >> b;
    solve(a - 1, cnt1), solve(b, cnt2);
    for (int i = 0; i <= 9; i++)
        cout << cnt2[i] - cnt1[i] << ' ';
    cout << endl;
}

状态压缩 DP

91. 最短Hamilton路径 - AcWing题库

dp[i][j] 表示集合 i 内的 最短 Hamilton 路径，即从起点 0 出发，经过 i 中的所有点，到达终点 j 时的最短路径

int n, dp[1 << 20][21];
int dist[21][21];int main()
{
    memset(dp, 0x3f, sizeof dp);
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> dist[i][j];    dp[1][0] = 0;
    for (int i = 1; i < (1 << n); i++)
        for (int j = 0; j < n; j++)
            if ((i >> j) & 1)	//	判断当前的集合 i 是否含有 j 点
                for (int k = 0; k < n; k++)
                    if ((i ^ (1 << j)) >> k & 1)	//	(i ^ (1 << j))从集合中去掉 j 点，得到集合 i - j，然后 >> k & 1 表示用 k 遍历集合中的 1，这些 1 就是 i - j 中的点，实现枚举集合 i - j 中的所有点 
                        dp[i][j] = min(dp[i][j], dp[i ^ (1 << j)][k] + dist[k][j]);    cout << dp[(1 << n) - 1][n - 1];
}

区间 DP

计数 DP

树形 DP

一般优化

单调队列优化

四边形不等式优化

斜率优化/凸壳优化

例题

例题 1

Problem - 6024 (hdu.edu.cn)

struct node
{
    int x, c;
    bool operator<(const node &a) const
    {
        return x < a.x;
    }
};// dp[i][0]为到第i个教室且第i个教室不建糖果店的花费前缀和，dp[i][1]为到第i个教室且第i个教室建糖果店的花费前缀和
int dp[N][2];void solve()
{
    int n;
    while (cin >> n)
    {
        vector<node> a(n + 1);
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i].x >> a[i].c;
            dp[i][0] = dp[i][1] = INF;
        }
        sort(a.begin() + 1, a.end()); // 按坐标排序
        dp[1][1] = a[1].c;
        dp[1][0] = INF;
        for (int i = 2; i <= n; i++)
        {
            int sum = 0;
            dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]) + a[i].c; // i教室建店此处一定花费a[i].c，所以再加上之前较优的花费
            for (int j = i - 1; j >= 1; j--)
            {
                sum += (i - j) * (a[j + 1].x - a[j].x);   // sum为从j+1教室到i教室的花费和
                dp[i][0] = min(dp[i][0], dp[j][1] + sum); // 判断j教室建店是不是最优
            }
        }
        cout << min(dp[n][0], dp[n][1]) << endl;
    }
}

例题 2

Problem - 5492 (hdu.edu.cn)

\[(n+m-1)\sum_{i=1}^{n+m-1}(A_i-A_{avg})^2=(n+m-1)*\sum_{i=1}^{n+m-1}A_i^2-(\sum_{i=1}^{n+m-1}A_i)^2 \]

int kase;
//dp[i][j][k] 代表从 (1, 1) 走到 (i, j) 且路径的和为 k 的最小平方和
int dp[35][35][2050];void solve()
{
    int n, m;
    cin >> n >> m;
    vector<vector<int> > a(n + 1, vector<int>(m + 1));
    int sum = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j], sum += a[i][j];    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= m; j++)
            for (int k = 0; k <= 2000; k++)
                dp[i][j][k] = inf;
    dp[0][1][0] = dp[1][0][0] = 0;    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            for (int k = a[i][j]; k <= 2000; k++)
                dp[i][j][k] = min(dp[i - 1][j][k - a[i][j]] + a[i][j] * a[i][j], dp[i][j - 1][k - a[i][j]] + a[i][j] * a[i][j]);    int ans = inf;
    for (int i = 0; i <= 2000; i++)
        ans = min(1LL * ans, (n + m - 1) * dp[n][m][i] - i * i);
    cout << "Case #" << ++kase << ": " << ans << endl;
}
http://www.sczhlp.com/news/685.html

相关文章：

  • Wireshark入门指南：网络流量分析利器
  • 量子计算先驱David Schuster的二十年探索之路
  • SpringBoot中使用TOTP实现MFA（多因素认证） - Tom
  • 上拉电阻和下拉电阻
  • 蓝桥杯2024省赛A组题解
  • 春训#2题解
  • 国内AI编码工具哪家强CodeBuddy+通义灵码+Trae
  • js基础第二天
  • [PaperReading] Stable Video Diffusion: Scaling Latent Video Diffusion Models to Large Datasets
  • 蓝桥杯2025省赛A组游记题解
  • 7.28 闲话
  • FM2023利兹联崛起之路#1
  • 暑训#1补题
  • 07.08 论文精读 人像线稿生成模型
  • 7/28
  • 【LeetCode 141】算法：环形链表
  • 暑训#3补题
  • 关于跨域的一点新理解
  • js基础第三天
  • 龙哥量化：股票期货- 精华资料目录
  • 2025省选组合数学笔记
  • 字符串
  • js基础第四天
  • 同时点亮LED、数码管以及点阵
  • 今日总结
  • docker安装
  • 二进制简史：从理论到芯片
  • Qcom dcvs_epss.c 驱动解析.
  • AirSim+PX4+QGC实现无人机自动避障
  • js基础第五天