好的，根据你的要求，我从线性动态规划领域中随机挑选一个还未在已提供列表中出现过的经典题目来讲解。

题目：一和零（Ones and Zeroes）

题目描述：

你面前有一个数组 strs，其中的每个元素都是一个二进制字符串（仅由字符 '0' 和 '1' 组成）。

同时，你拥有 m 个 0 和 n 个 1。

你的任务是：找出并返回 strs 的一个最大子集的大小，该子集中所有字符串的 '0' 的总数不超过 m，'1' 的总数不超过 n。

换句话说，你可以从数组中选取若干个字符串，但是你所选的所有字符串中，字符 '0' 的总数不能超过 m，字符 '1' 的总数不能超过 n。你需要最大化选取字符串的个数。

示例 1：

输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多可以选出 4 个字符串，使得它们包含的 ‘0’ 和 ‘1’ 总数不超过限制。
一种可行的子集是 {"10", "0001", "1", "0"}。
其中 “10” 有 1个0，1个1； “0001”有3个0，1个1； “1”有0个0，1个1； “0”有1个0，0个1。
总0数 = 1 + 3 + 0 + 1 = 5 <= m
总1数 = 1 + 1 + 1 + 0 = 3 <= n
注意，子集 {"111001"} 有 3个0和3个1，总和超过了 n=3 的限制，所以不可取。

示例 2：

输入：strs = ["10", "0", "1"], m = 1, n = 1
输出：2
解释：可以选取 {"0", "1"} 或 {"10"}，但无法选取全部三个。

解题过程详解

这个问题本质上是一个带有两个维度的“0-1背包问题”。在经典背包问题中，我们通常只有一个限制条件（背包容量），而这里有两个：0的数量限制 m 和 1的数量限制 n。每个字符串相当于一个物品，它的“重量”由两个数字构成（0的个数和1的个数），其“价值”是1（因为我们希望最大化选取的字符串数量）。

步骤1：分析问题与定义状态

1. 子问题定义：我们需要决定对于数组 strs 中的前 i 个字符串，在最多使用 j 个 0 和 k 个 1 的限制下，能构成的最大子集大小是多少？
2. 状态定义：我们可以定义一个三维动态规划数组 dp[i][j][k]。
   • i：表示我们考虑前 i 个字符串（i 从 1 到 strs.length）。
   • j：表示当前可用的 0 的数量（从 0 到 m）。
   • k：表示当前可用的 1 的数量（从 0 到 n）。
   • dp[i][j][k] 的值：表示在考虑前 i 个字符串，并且 0 的消耗不超过 j， 1 的消耗不超过 k 的条件下，所能选取的字符串的最大数量。

步骤2：确定状态转移方程

对于第 i 个字符串（假设其索引为 i-1），我们先计算出它包含多少 0（记为 zeros）和多少 1（记为 ones）。

对于状态 dp[i][j][k]，我们有两种选择：

1. 不选第 i 个字符串：

   • 那么最大子集大小就等于考虑前 i-1 个字符串时的结果，即 dp[i-1][j][k]。

2. 选第 i 个字符串（前提是 j >= zeros 且 k >= ones）：

   • 如果我们选择了这个字符串，那么我们就消耗了 zeros 个 0 和 ones 个 1。
   • 此时，我们能在前 i-1 个字符串中，使用剩下的 j - zeros 个 0 和 k - ones 个 1 来构建子集。
   • 这个子集的大小是 dp[i-1][j - zeros][k - ones]。
   • 因为当前我们选择了一个字符串，所以总大小要加1：dp[i-1][j - zeros][k - ones] + 1。

我们的目标是最大化子集大小，所以状态转移方程为：

dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j - zeros][k - ones] + 1)

其中，选择操作仅在 j >= zeros 且 k >= ones 时才有效，否则只能进行不选操作。

步骤3：初始化

当没有字符串可考虑时（i=0），无论有多少 0 和 1，能选出的字符串数量都是 0。
所以，对于所有的 j 和 k，dp[0][j][k] = 0。

步骤4：优化空间复杂度

观察状态转移方程，dp[i][...] 的值只依赖于 dp[i-1][...]。这是典型的滚动数组优化场景。

我们可以将三维数组压缩为二维数组 dp[j][k]。但需要注意，为了保证在计算 dp[j][k] 时，所依赖的 dp[j - zeros][k - ones] 是上一轮（i-1）的状态，我们需要从后向前遍历 j 和 k。这和使用一维数组解决经典0-1背包问题的技巧完全一致，只是这里有两个维度需要反向遍历。

优化后的状态定义：

• dp[j][k]：表示在 0 的数量限制为 j， 1 的数量限制为 k 的条件下，所能选取的字符串的最大数量。

状态转移方程（在二维数组中）：

对于每个字符串 s (包含 zeros 个0， ones 个1)：
    for (int j = m; j >= zeros; j--) {
        for (int k = n; k >= ones; k--) {
            dp[j][k] = max(dp[j][k], dp[j - zeros][k - ones] + 1);
        }
    }

初始化时，dp 数组所有元素为 0。

步骤5：算法流程与最终答案

1. 创建一个大小为 (m+1) x (n+1) 的二维数组 dp，并全部初始化为 0。
2. 遍历 strs 数组中的每一个字符串 s：
   • 统计 s 中字符 '0' 的个数 zeros 和字符 '1' 的个数 ones。
   • 逆序 遍历 j 从 m 到 zeros，并且 逆序 遍历 k 从 n 到 ones：
     • 更新 dp[j][k] = max(dp[j][k], dp[j - zeros][k - ones] + 1)。
3. 遍历结束后，dp[m][n] 的值就是我们想要的最大子集的大小。

最终答案：dp[m][n]

举例说明（以示例1简化版）

假设 strs = ["10", "0"], m = 1, n = 1。

初始化 dp 数组（m+1=2行， n+1=2列）：

dp = [
    [0, 0],
    [0, 0]
]

处理第一个字符串 "10"：

• zeros = 1, ones = 1
• 逆序遍历 j 和 k：
  • j=1, k=1： dp[1][1] = max(dp[1][1]=0, dp[0][0]+1=1) = 1
  • j=1, k=0： k < ones(1)，内层循环不执行。
  • j=0, ...： j < zeros(1)，外层循环结束。
• 此时 dp 为：

[
    [0, 0],
    [0, 1]
]

处理第二个字符串 "0"：

• zeros = 1, ones = 0
• 逆序遍历：
  • j=1, k=1： dp[1][1] = max(dp[1][1]=1, dp[0][1]+1=1) = 1 （保持不变）
  • j=1, k=0： dp[1][0] = max(dp[1][0]=0, dp[0][0]+1=1) = 1
  • j=0, ...： j < zeros(1)，结束。
• 最终 dp 为：

[
    [0, 0],
    [1, 1]
]

最终答案 dp[1][1] = 1。解释：我们只能选 "10" 或者 "0" 中的一个，不能同时选两个，因为两个 0 的总数（1+1=2）会超过 m=1 的限制。

这个例子清晰地展示了二维背包的动态规划过程。