动态规划 · Zwing's blog

0-1 背包问题

给定一个容量为 \(V\) 的背包和 \(n\) 个物品，每个物品有一个体积 \(w_i\) 和价值 \(val_i\)，求在不超过背包容量的情况下，背包内物品的最大价值

状态转移方程

\(dp[i][j]\) 表示前 \(i\) 个物品在容量不超过 \(j\) 的情况下，背包内物品的最大价值

dp[i][j] = \max(dp[i-1][j], dp[i-1][j-w_i] + val_i)

无论当前物品是否放入背包，前 \(i-1\) 个物品的最大价值是确定的，且由于每个物品只有一个只能从 dp[i-1][] 转移过来

代码实现

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int V, N;
    cin >> V >> N;
    vector<pair<int,int>> bag(N+1);
    for (int i = 1; i <= N; i++)
    {
        cin >> bag[i].first >> bag[i].second;
    }

    vector dp(N + 1, vector(V + 1, 0));
    for (int i = 1; i <= N; i++)
    {
        int w = bag[i].first;
        int val = bag[i].second;
        for (int j = 0; j <= V; j++)
        {
            if (j >= w)
            {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w]+val);
            }
            else // 装不下只能等于不装这个的值
            {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    cout << dp[N][V];
}

优化

将二维数组优化为一维数组，因为 \(dp[i][j]\) 只与 \(dp[i-1][j]\) 和 \(dp[i-1][j-w]\) 有关，所以可以倒序遍历 \(j\)，防止覆盖

理解这个问题的核心在于：一维数组本质上是在不断 “覆盖” 自己

当我们把 dp[i][j] 压缩成 dp[j] 时，数组里的值在某一时刻，其实混合了 “上一轮循环（第 i-1 个物品）” 和 “这一轮循环（第 i 个物品）” 的数据

(1) 核心矛盾：新值还是旧值？

在 0-1 背包的二维逻辑中：

注意：等号右边的两个状态 dp[i-1][...] 都属于上一行（即还没放第 i 件物品时的状态）

(2) 模拟过程：为什么正序会出错？

假设我们要更新第 i 件物品，它的重量 w = 2，价值 v = 10。

如果正序遍历 j = 2 to 10：

当 j = 2 时：dp[2] = max(dp[2], dp[2-2] + 10)。此时 dp[2] 更新成了包含物品 i 的值
当 j = 4 时：dp[4] = max(dp[4], dp[4-2] + 10)

问题来了！ 这里的 dp[4-2]（即 dp[2]）已经在第 1 步里被更新过了。
它现在代表的是“已经放了一个物品 i”的状态。
如果你用它来更新 dp[4]，就相当于在已经放了一个物品 i 的基础上，又放了一个物品 i。

这就是“完全背包”（物品可以无限用）的逻辑，而不是“0-1 背包”。

(3) 模拟过程：为什么逆序就对了？

如果逆序遍历 j = 10 down to 2：

当 j = 10 时：dp[10] = max(dp[10], dp[10-2] + 10)。这里的 dp[8] 还是上一轮循环留下来的旧值，因为它还没被这一轮的 j 扫到。
当 j = 8 时：dp[8] = max(dp[8], dp[8-2] + 10)。这里的 dp[6] 同样也是上一轮的旧值。

逆序保证了：当你计算 dp[j] 需要用到 dp[j-w] 时，dp[j-w] 绝对还没被这一轮循环修改过。它依然代表“只考虑前 i-1 个物品”时的最优解。

(4) 形象的比喻

想象你在改一张成绩单（数组）：

正序：你从左往右改。改到右边的人时，你参考了左边已经改好的新分数。这导致错误地叠加了信息。
逆序：你从右往左改。当你改到右边的人时，你回头看的左边所有人，都还是没被改动过的旧分数。这保证了你参考的信息是纯净的 “上一版”。

总结对照表

遍历方向	对应的逻辑	物品可选次数	备注
二维数组 (任意顺序)	`dp[i][j]` 明确指向 `i-1`	1次	最稳妥，费空间
一维数组 + 逆序	确保拿到的 `dp[j-w]` 是旧数据	1次 (0-1背包)	最推荐，省空间
一维数组 + 正序	拿到的 `dp[j-w]` 可能是新数据	无数次 (完全背包)	用于不同题型

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int V, N;
    cin >> V >> N;
    vector<pair<int,int>> bag(N+1);
    for (int i = 1; i <= N; i++)
    {
        cin >> bag[i].first >> bag[i].second;
    }

    vector dp(V + 1, 0);
    for (int i = 1; i <= N; i++)
    {
        int w = bag[i].first;
        int val = bag[i].second;
        for (int j = V; j >= 0; j--)
        {
            if (j >= w)
            {
                dp[j] = max(dp[j-w]+val, dp[j]);
            }
        }
    }
    cout << dp[V];
}

方案数问题

凑出给定值的方案数

\(dp[i][j]\)：表示使用前 \(i\) 种纸币凑出金额 \(j\) 的方案总数

对于第 \(i\) 种纸币（面额为 \(a_i\)），我们要凑出金额 \(j\)，方案可以分为两大类：

不使用第 \(i\) 种纸币。既然不用第 \(i\) 种，那么金额 \(j\) 必须全部由前 \(i-1\) 种纸币凑齐。方案数 = \(dp[i-1][j]\)
至少使用一张第 \(i\) 种纸币。如果我们已经确定选了一张 \(a_i\)，那么剩下的金额就是 \(j - a_i\)。方案数 = \(dp[i-1][j - a_i]\)

综合转移方程：

\[dp[i][j] = (dp[i-1][j] + dp[i-1][j - a_i])\]

(条件：当 \(j \ge a_i\) 时；若 \(j < a_i\)，则 \(dp[i][j] = dp[i-1][j]\))

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, w;
    cin >> n >> w;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    vector dp(n+1, vector(w+1, 0));
    for (int i = 0; i <= n; i++)
    {
        dp[i][0] = 1;
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= w; j++)
        {
            if (j >= a[i])
            {
                dp[i][j] = dp[i-1][j] + dp[i-1][j-a[i]];
            }
            else
            {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    cout << dp[n][w];
}

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, w;
    cin >> n >> w;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    vector dp(w+1, 0);
    dp[0] = 1;

    for (int i = 1; i <= n; i++)
    {
        for (int j = w; j >= 0; j--)
        {
            if (j >= a[i])
            {
                dp[j] = dp[j] + dp[j-a[i]];
            }
        }
    }
    cout << dp[w];
}

当然，如果只是求能不能凑出而不是方案数，应该简单的做法就是照搬上面再返回 dp > 0，但这种情况下 dp 数组中的值可能极大，使用或运算取代加法即可

完全背包问题

标准完全背包问题

与 0-1 背包问题类似，但是每个物品可以取无限次

状态转移方程

\(dp[i][j]\) 表示前 \(i\) 个物品在容量不超过 \(j\) 的情况下，背包内物品的最大价值

dp[i][j] = \max(dp[i-1][j], dp[i][j-w_i] + val_i)

与 0-1 背包问题不同的是，当前物品可以取多次，\(dp[i][j]\) 从 \(dp[i][j-w_i] + val_i\) 转移过来即意为着重复取当前物品

代码实现

与 0-1 背包的唯一区别在于转移方程处从 i-1 到 i 的修改

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int V, N;
    cin >> V >> N;
    vector<pair<int,int>> bag(N+1);
    for (int i = 1; i <= N; i++)
    {
        cin >> bag[i].first >> bag[i].second;
    }

    vector dp(N + 1, vector(V + 1, 0));
    for (int i = 1; i <= N; i++)
    {
        int w = bag[i].first;
        int val = bag[i].second;
        for (int j = 0; j <= V; j++)
        {
            if (j >= w)
            {
                dp[i][j] = max(dp[i-1][j], dp[i][j-w]+val);
            }
            else // 装不下只能等于不装这个的值
            {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    cout << dp[N][V];
}

优化

与 0-1 背包不同的是这里允许覆盖，正序遍历

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int V, N;
    cin >> V >> N;
    vector<pair<int,int>> bag(N+1);
    for (int i = 1; i <= N; i++)
    {
        cin >> bag[i].first >> bag[i].second;
    }

    vector dp(V + 1, 0LL);
    for (int i = 1; i <= N; i++)
    {
        int w = bag[i].first;
        int val = bag[i].second;
        for (int j = 0; j <= V; j++)
        {
            if (j >= w)
            {
                dp[j] = max(dp[j-w]+val, dp[j]);
            }
        }
    }
    cout << dp[V];
}

方案数问题

[凑出给定值的方案数]

\(dp[i][j]\)：表示使用前 \(i\) 种纸币凑出金额 \(j\) 的方案总数

对于第 \(i\) 种纸币（面额为 \(a_i\)），我们要凑出金额 \(j\)，方案可以分为两大类：

不使用第 \(i\) 种纸币既然不用第 \(i\) 种，那么金额 \(j\) 必须全部由前 \(i-1\) 种纸币凑齐。方案数 = \(dp[i-1][j]\)
至少使用一张第 \(i\) 种纸币如果我们已经确定选了一张 \(a_i\)，那么剩下的金额就是 \(j - a_i\)。由于第 \(i\) 种纸币有无限张，剩下这部分金额依然可以从前 \(i\) 种纸币中挑选。方案数 = \(dp[i][j - a_i]\)（与 0-1 背包唯一区别之处）

综合转移方程：

dp[i][j] = (dp[i-1][j] + dp[i][j - a_i]) \pmod{10^9+7}

(条件：当 \(j \ge a_i\) 时；若 \(j < a_i\)，则 \(dp[i][j] = dp[i-1][j]\))

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, w;
    cin >> n >> w;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    vector dp(n+1, vector(w+1, 0));
    for (int i = 0; i <= n; i++)
    {
        dp[i][0] = 1;
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= w; j++)
        {
            if (j >= a[i])
            {
                dp[i][j] = dp[i-1][j] + dp[i][j-a[i]];
            }
            else
            {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    cout << dp[n][w];
}

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, w;
    cin >> n >> w;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    vector dp(w+1, 0);
    dp[0] = 1;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= w; j++)
        {
            if (j >= a[i])
            {
                dp[j] = dp[j] + dp[j-a[i]];
            }
        }
    }
    cout << dp[w];
}

最小化代价问题

凑出给定值的最小张数

\(dp[i][j]\)：表示用前 \(i\) 种纸币凑出金额 \(j\) 所需的最少张数

对于第 \(i\) 种纸币（面额为 \(a_i\)），在凑金额 \(j\) 时，我们有两种选择：

不使用第 \(i\) 种纸币：那么我们必须只用前 \(i-1\) 种纸币凑出金额 \(j\)。此时：\(dp[i][j] = dp[i-1][j]\)
至少使用一张第 \(i\) 种纸币：如果我们选了一张 \(a_i\)，那么剩下的金额就是 \(j - a_i\)。由于每种纸币可以无限次使用，剩下的金额 \(j - a_i\) 依然可以从前 \(i\) 种纸币中选择。此时：\(dp[i][j] = dp[i][j - a_i] + 1\)。

综合转移方程：

dp[i][j] = \min(dp[i-1][j], \quad dp[i][j - a_i] + 1)

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, w;
    cin >> n >> w;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    // 由于求最小，初始化为一个大数，表示不可达
    vector dp(n + 1, vector(w + 1, 1e9));
    for (int i = 0; i <= n; i++)
    {
        dp[i][0] = 0; // 凑 0 需要 0 张纸币
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= w; j++)
        {
            if (j >= a[i])
            {
                dp[i][j] = min(dp[i][j-a[i]] + 1, dp[i-1][j]);
            }
            else
            {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    cout << dp[n][w];
}

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, w;
    cin >> n >> w;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    // 由于求最小，初始化为一个大数，表示不可达
    vector dp(w + 1, 1e9);
    dp[0] = 0;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= w; j++)
        {
            if (j >= a[i])
            {
                dp[j] = min(dp[j-a[i]] + 1, dp[j]);
            }
        }
    }
    cout << dp[w];
}

两层遍历的顺序问题

这是一个非常深刻的问题。在背包 DP 中，改变嵌套循环的顺序往往会直接改变你所求解的问题性质：是组合（Combination）还是排列（Permutation）

以下以完全背包为例：

外层循环物品，内层循环容量（求组合）

for (int i = 0; i < n; i++) { // 外层：遍历每一种纸币
    for (int j = a[i]; j <= w; j++) { // 内层：遍历金额
        dp[j] = (dp[j] + dp[j - a[i]]);
    }
}

逻辑含义：我们是一个物品一个物品地处理。当我们在处理第 i 种纸币时，我们更新了所有可能的金额。这意味着，对于任何一个金额 j，里面的组合一定是按照纸币出现的先后顺序排列的
结果：它计算的是组合数
例子：如果要凑出 3 元，你有面额 1 和 2。这种写法只会产生 {1, 2} 这一种情况，而不会出现 {2, 1}。因为当程序处理面额 2 时，面额 1 的计算已经完全结束了，2 只可能加在 1 的后面

外层循环容量，内层循环物品（求排列）

完全背包排列方案数

如果你把循环顺序反过来：

for (int j = 1; j <= w; j++) { // 外层：遍历金额
    for (int i = 0; i < n; i++) { // 内层：遍历每一种纸币
        if (j >= a[i]) {
            dp[j] = (dp[j] + dp[j - a[i]]);
        }
    }
}

逻辑含义：我们在计算金额 j 时，尝试了最后一张纸币可能是 \(a[0], a[1], \dots, a[n]\) 中的任何一种
结果：它计算的是排列数（考虑顺序）
例子：如果要凑出 3 元，面额有 1 和 2
计算 dp[3] 时，最后一张可以是 1（剩下 dp[2] 的方案：{1,1} 或 {2}），也可以是 2（剩下 dp[1] 的方案：{1}）
最终会得到：{1,1,1}, {2,1}, {1,2}。这里 {2,1} 和 {1,2} 被视为不同的方案

求排列时用一维数组，因为此时完全不考虑 “前面用了几个数”，只考虑剩余量

核心区别对比

循环顺序	关注点	典型应用场景
外物内容	“这个物品我要用几次？”	组合问题、普通的背包最大价值、P2834 纸币组合数
外容内物	“凑成这个金额的最后一步是什么？”	排列问题、爬楼梯问题（先迈 1 步还是 2 步顺序不同）

为什么对 “最值问题” 没影响？

原因：求 min 或 max 是具有交换律的。
不管你是先拿 1 元再拿 5 元，还是先拿 5 元再拿 1 元，张数都是 2 张。
但是对于 P2834（方案总数），顺序就至关重要了，因为题目要求的是“有多少种组合”，通常隐含意思是不计顺序。如果计顺序，题目通常会说明“不同的支付次序视为不同方案”。

总结建议

0/1 背包：必须外层物品，内层容量（且内层要逆序），因为每个物品只能用一次
完全背包 - 求最值：内外层顺序通常可以互换
完全背包 - 求方案数：
- 求组合（不计顺序）：外层物品，内层容量
- 求排列（计顺序）：外层容量，内层物品

其他

注意数组越界问题和初始化问题
考虑需不需要将 dp 数组开为 long long
考虑需不需要状态压缩