算法讲解069 必备 从递归入手三维动态规划

来源：算法讲解069【必备】从递归入手三维动态规划　·　2026-11-03

依据：视频字幕 2000 字

一句话概括

三维动态规划（3D DP）就是在二维 DP 的基础上再多一个可变参数，用「递归 → 记忆化搜索 → 严格位置依赖 → 空间压缩」这条固定流水线处理多约束选择问题（典型：多维费用背包）。

它解决什么问题

给定若干物品，每个物品有多个维度的「费用」（比如 0 的个数、1 的个数），每个维度的总费用有上限，问最多能选多少个物品（或最大价值）。本质是多维费用 0-1 背包：每个物品选/不选，多个维度都不能超限。

基础知识（前置概念，用大白话解释）

• 可变参数：递归函数里会变化的参数。一个可变参数能完全决定返回值 → 一维 DP；两个 → 二维 DP；三个 → 三维 DP。
• 记忆化搜索（memoization）：递归时把算过的 (参数组合) → 返回值 存表，下次直接查，避免重复计算。
• 严格位置依赖：递归里 f(i, ...) 只依赖 f(i+1, ...)，即后面的状态只由更靠后的状态推出，于是可以改成从后往前的迭代填表。
• 空间压缩：如果第 i 层只依赖第 i+1 层，就可以只保留两层（滚动数组），把 i 这一维压掉。
• 多维费用背包：背包问题里「费用」不止一个维度（重量 + 体积 + …），每个维度都有容量上限。

原理（为什么这么做是对的，尽量给直觉）

对每个物品只有两种命运：选或不选。

• 不选第 i 个：答案 = f(i+1, z, o)。
• 选第 i 个（前提是它的 0 个数 ≤ z 且 1 个数 ≤ o）：答案 = 1 + f(i+1, z - zero_i, o - one_i)。

两者取 max，就是「从第 i 个往后自由选择、在剩余容量 z、o 下最多能选几个」。

为什么可以记忆化：f(i, z, o) 的返回值只由这三个参数决定，与「怎么走到这个状态」无关（无后效性），所以同一个三元组算一次就够。

为什么能压维：f(i, ·, ·) 只用到 f(i+1, ·, ·)，所以从 i = n-1 倒着推到 i = 0，只需保留「下一层」的二维表，滚动更新即可。注意 0-1 背包压维时内层容量要倒序枚举，否则同一物品会被重复选（变成完全背包）。

步骤（编号，可照着写）

1. 预处理每个字符串的 0 个数 zeros[i]、1 个数 ones[i]。
2. 写暴力递归 f(i, z, o)：i == n 返回 0；不选 = f(i+1, z, o)；能选则 max(不选, 1 + f(i+1, z-zeros[i], o-ones[i]))。
3. 加记忆化：三维 memo[i][z][o]，初值 -1，算过直接返回。
4. 改严格位置依赖：从 i = n-1 到 0 倒推，dp[i][z][o] = max(dp[i+1][z][o], 1 + dp[i+1][z-zeros[i]][o-ones[i]])（能选时）。
5. 空间压缩：只留两层 cur[z][o]、next[z][o]，或直接一维滚动（内层 z、o 倒序）。
6. 答案 = dp[0][M][N]。

样例（一个具体小例子，带每步变化）

strs = ["10","0","1"]，M=1（最多 1 个 0），N=1（最多 1 个 1）。

预处理：zeros = [1,1,0]，ones = [1,0,1]。

从 i=2 倒推（dp[i][z][o]，z∈[0,1]，o∈[0,1]）：

• i=2（"1"，zero=0, one=1）：

- dp[2][z][o]：o≥1 时可选 → 1；o=0 时 → 0。

- 表：dp[2][0][0]=0, dp[2][0][1]=1, dp[2][1][0]=0, dp[2][1][1]=1。

• i=1（"0"，zero=1, one=0）：

- dp[1][0][0]=0；dp[1][0][1]=dp[2][0][1]=1；

- dp[1][1][0]=max(dp[2][1][0], 1+dp[2][0][0])=max(0,1)=1；

- dp[1][1][1]=max(dp[2][1][1], 1+dp[2][0][1])=max(1,2)=2。

• i=0（"10"，zero=1, one=1）：

- dp[0][1][1]=max(dp[1][1][1], 1+dp[1][0][0])=max(2,1)=2。

答案 = dp[0][1][1] = 2（选 "0" 和 "1"，或 "10" 单独一个，最大是 2）。✓

代码（Python 一份：好读、用于理解；C++ 一份：竞赛风，能直接抄进比赛，带注释，不用玄学宏）

Python（记忆化，好读）：

def findMaxForm(strs, M, N):
    n = len(strs)
    zeros = [s.count('0') for s in strs]
    ones  = [s.count('1') for s in strs]
    from functools import lru_cache

    @lru_cache(maxsize=None)
    def f(i, z, o):
        if i == n:
            return 0
        best = f(i + 1, z, o)                      # 不选
        if zeros[i] <= z and ones[i] <= o:         # 选
            best = max(best, 1 + f(i + 1, z - zeros[i], o - ones[i]))
        return best

    return f(0, M, N)

C++（严格位置依赖 + 空间压缩，竞赛风）：

#include <bits/stdc++.h>
using namespace std;

// 一和零：最多 M 个 0、N 个 1，最多能选多少个字符串
int findMaxForm(vector<string>& strs, int M, int N) {
    int n = (int)strs.size();
    vector<int> zeros(n), ones(n);
    for (int i = 0; i < n; i++) {
        for (char c : strs[i]) {
            if (c == '0') zeros[i]++;
            else          ones[i]++;
        }
    }
    // dp[z][o]：当前层（i+1 往后）在容量 z、o 下的最大选择数
    vector<vector<int>> dp(M + 1, vector<int>(N + 1, 0));
    for (int i = n - 1; i >= 0; i--) {
        int z0 = zeros[i], o0 = ones[i];
        // 0-1 背包压维：z、o 必须倒序，防止同一物品被重复选
        for (int z = M; z >= z0; z--) {
            for (int o = N; o >= o0; o--) {
                dp[z][o] = max(dp[z][o], 1 + dp[z - z0][o - o0]);
            }
        }
    }
    return dp[M][N];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<string> strs = {"10", "0", "1"};
    cout << findMaxForm(strs, 1, 1) << "\n";  // 2
    return 0;
}

复杂度（时间/空间，最好/平均/最坏，顺带说常数大不大）

• 时间：O(n · M · N)，n 为字符串个数，M、N 为两个容量上限。最好/平均/最坏同阶。
• 空间：记忆化 O(n·M·N)；严格位置依赖 O(n·M·N)；空间压缩后 O(M·N)。
• 常数：三维表访问是连续内存（vector 嵌套），常数小；压维后内层倒序循环，缓存友好。n、M、N 都到 1e2~1e3 量级时 n·M·N 可能到 1e8~1e9，注意常数和是否超时。

竞赛里什么时候用（看到什么题面特征就该想到它）

• 物品有多个维度的费用，每个维度都有上限（「最多 M 个 0、N 个 1」「重量 + 体积」「时间 + 金钱」）。
• 每个物品选/不选（0-1 性质），问最多选几个 / 最大价值。
• 递归里出现三个会变的参数（位置 i + 两个剩余容量），且 f(i, ...) 只依赖 f(i+1, ...)。
• 题面数据规模提示 n·M·N 在可接受范围（约 1e7~1e8）。

竞赛模板（C++，可直接背下来的写法；变量名清楚）

// 通用三维 0-1 背包（多维费用）压维模板
// items: 每个物品的费用向量 cost[i] = {c1, c2, ...}
// cap:   每个维度的容量上限
// 返回：最多能选多少个物品
int multiDimKnapsack(const vector<vector<int>>& cost, const vector<int>& cap) {
    int n = (int)cost.size();
    int d = (int)cap.size();
    // 这里以 d == 2 为例，d 更大时用扁平数组或递归处理
    int C1 = cap[0], C2 = cap[1];
    vector<vector<int>> dp(C1 + 1, vector<int>(C2 + 1, 0));
    for (int i = 0; i < n; i++) {
        int a = cost[i][0], b = cost[i][1];
        for (int x = C1; x >= a; x--)
            for (int y = C2; y >= b; y--)
                dp[x][y] = max(dp[x][y], 1 + dp[x - a][y - b]);
    }
    return dp[C1][C2];
}

边界与易错点（WA 的常见原因，越具体越好）

• 压维后内层没倒序：z、o 正序枚举会让同一物品被多次选，答案偏大（变成完全背包）。
• 容量下标从 0 开始：dp 大小是 M+1 × N+1，循环上界是 M、N，别写成 M-1。
• 能选的条件写反：必须 zeros[i] <= z && ones[i] <= o 才能选，漏判会越界或算错。
• 字符串里不是只有 '0'/'1'：题面保证只有 0/1，但统计时用 c == '0' 而非 c != '1' 更稳。
• 多测没清空：多组数据时 dp 要重新初始化为 0（压维版每轮新建即可）。
• M 或 N 为 0：容量为 0 时只能选费用全 0 的物品，循环 z >= z0 在 z0=0 时仍会执行，注意别死循环。
• 答案取 dp[M][N] 而非 dp[0][0]：压维版最终状态在满容量处。

同类题 / 变形（说清楚怎么改）

• 最大价值而非个数：把 1 + dp[...] 换成 value[i] + dp[...]，max 不变。
• 恰好装满：初始化 dp 为 -INF，dp[0][0]=0，最后看 dp[M][N] 是否 -INF。
• 完全背包（物品可重复选）：压维时内层容量正序枚举。
• 三维以上费用：把 dp 换成三维/扁平数组，最内层倒序，思路完全一样。
• 分组背包：外层枚举组，组内枚举物品，容量倒序。

常见坑

• 用 map/list 存 DP 表，常数爆炸，1e5 规模直接 TLE；一律用 vector。
• #define int long long 导致 vector 下标类型混乱，别用；需要 64 位就显式 long long。
• 记忆化用 unordered_map 存三元组 key，哈希常数大；规模允许时用定长三维数组。
• 递归深度过大（n 到 1e5）栈溢出；改迭代或手动栈。
• 多测时全局 memo 没重置，答案串组。

拓展（变体、实际用途、面试常问）

• 实际用途：资源分配（预算 + 人力 + 时间多约束）、广告投放选品、云资源打包。
• 面试常问：LeetCode 474「一和零」就是本题原题；「二维费用背包」是 0-1 背包的标准变体。
• 变体：多维费用 + 分组、多维费用 + 依赖（树形背包）、多维费用 + 计数（求方案数，把 max 换成加法并取模）。
• 优化方向：当某一维容量很大但物品费用稀疏时，可用「按费用分组 + 前缀和」或「bitset 加速可达性」。

自测 3 题（题目 + 折叠答案）

题 1：strs = ["10","0001","111001","1","0"]，M=5，N=3，最多选几个？