算法模式：变治法

D瓜哥
算法
算法模式：变治法

在上一篇文章 算法模式：分治法 介绍一种可用于处理节点前后顺序的算法模式：拓扑排序。本篇文章，介绍一种有魔力的，可以将复杂问题化繁为简，化腐朽为神奇的算法模式：变治法。

变治法

D瓜哥最早知道变治法也是在 《算法设计与分析基础》 中。这里也直接引用该书的介绍。

变治法，就是基于变换的一种思想方法，首先把问题的实例变得容易求解，然后进行求解。

变治法的工作可以分成两个阶段：首先把问题变得更容易求解，然后对实例进行求解。根据我们对问题实例的变换方式，变治思想有3种主要的类型：

  1. 实例化简(Instance simplification) — 指将原问题变换为同样问题的一个更简单或者更方便的实例。一个典型的案例是：去重时，先排序，

    1. 列表预排序

      1. 检验数组中元素的唯一性

      2. 模式计算

      3. 查找问题

    2. 高斯消元法

      1. 系数矩阵的LU分解(LU decomposition)

      2. 计算矩阵的逆

      3. 计算矩阵的行列式

    3. AVL 树

  2. 改变表现(Representation Change) — 指将原问题变换为同样实例的不同表现。经典的栗子：霍纳法则。

    1. 多路平衡查找树（最简单的情况：2-3树）

    2. 求多项式的霍纳法则

    3. 两种二进制幂算法

    4. 堆排序

  3. 问题化简(Problem reduction) — 指把一个给定的问题变换为另一个可以用已知算法求解的问题。（归化思想）转换的难题在于如何找到一个变换的目标算法。典型案例是背包问题，背包问题的本质是线性规划。了解了线性规划的本质后，才能更好地解决高维的背包问题。

    1. 求最小公倍数

    2. 计算图中的路径数量

    3. 最优化问题（最大化问题(maximization problem)、最小化问题(minimization problem)）

    4. 线性规划（单纯形法、0/1背包问题）

    5. 简化为图问题

LeetCode 474. 一和零

LeetCode - 474. 一和零

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

示例 1：

输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

示例 2：

输入：strs = ["10", "0", "1"], m = 1, n = 1
输出：2
解释：最大的子集是 {"0", "1"} ，所以答案是 2 。

提示：

  • 1 <= strs.length <= 600

  • 1 <= strs[i].length <= 100

  • strs[i] 仅由 0 和 1 组成

  • 1 <= m, n <= 100

思路分析

把题目中的 0 和 1 的个数视为背包的容量，每一个字符串视为装进背包的物品。这道题就可以使用 0-1 背包问题的思路完成，这里的目标值是能放进背包的字符串的数量。

使用线性规划来描述问题如下：

\$使 sum_(i=1)^n x_i 最大\$
\$约束条件：\$
\$sum_(i=1)^n Z_i*x_i = m\$
\$sum_(i=1)^n O_i*x_i = n\$
\$x_i in {0, 1}\$
\$j = 1,...,n\$

代码如下：

/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2025-04-08 20:44:04
 */
public int findMaxForm(String[] strs, int m, int n) {
  // 计算每个字符串中 0 和 1 的数量
  int length = strs.length;
  int[][] bits = new int[length][2];
  for (int i = 0; i < length; i++) {
    for (char c : strs[i].toCharArray()) {
      bits[i][c - '0']++;
    }
  }
  // 1、确定 dp 数组（dp table）以及下标的含义
  //   ① 表示此时处理的字符串
  //   ② 表示此时 0 的个数，即 0 的数量限制
  //   ③ 表示此时 1 的个数，即 1 的数量限制
  // (x, y, z) 指的是到达第 x 个字符串时，
  // 如果有 y 个 0 和 z 个 1，那么最大子集数量
  // 3、dp 数组如何初始化
  //   由于不能为负数，最初都没有选择，则全部初始化为 0
  int[][][] dp = new int[length + 1][m + 1][n + 1];
  // 4、确定遍历顺序
  //   从第一个字符串开始遍历
  for (int x = 1; x <= length; x++) {
    int zeros = bits[x - 1][0];
    int ones = bits[x - 1][1];
    for (int y = 0; y <= m; y++) {
      for (int z = 0; z <= n; z++) {
        // 2、确定递推公式
        //  dp[x][y][z] = max(dp[x][y][z], dp[x-1][y - zeros][z - ones] + 1);
        if (y >= zeros && z >= ones) {
          // 在加入当前字符串和不加入当前字符串中选择其一
          dp[x][y][z] = Math.max(dp[x - 1][y][z], dp[x - 1][y - zeros][z - ones] + 1);
        } else {
          // 0 和 1 的容量不够，无法加入当前字符串，只能从上面继承
          dp[x][y][z] = dp[x - 1][y][z];
        }
      }
    }
  }
  return dp[length][m][n];
}
没有找到简单易懂的合适题目来实践该算法模式。这里暂且使用本题目来叙述。