记忆化搜索与状态压缩：优化递归与动态规划的利器

记忆化搜索是解决递归和动态规划问题的一种高效优化技术。它结合了递归的灵活性和动态规划的缓存思想，通过保存已经计算过的子问题结果，避免了重复计算，大幅提升了算法的效率。当问题状态复杂时，状态压缩技术可以进一步优化空间使用，尤其在处理大规模搜索问题时表现突出。本文将深入解析记忆化搜索的原理、应用，并结合状态压缩技术展示其在面试和算法竞赛中的常见应用。

1. 记忆化搜索的基本概念

1.1 什么是记忆化搜索？

记忆化搜索是一种递归与动态规划相结合的优化方法。它的核心思想是通过递归来解决问题，同时将已计算过的子问题结果保存起来（通常存储在数组或哈希表中），以便在后续调用时直接返回结果，避免重复计算。

1.2 记忆化搜索的应用场景

记忆化搜索常用于解决具有重叠子问题的递归问题。常见的应用场景包括：

• 斐波那契数列：通过记忆化避免重复计算同一层次的结果。

• 背包问题：在递归中缓存不同容量和物品选择的结果。

• 图论中的最短路径问题：如 TSP 问题，通过记忆化减少不必要的重复计算。

1.3 示例：记忆化斐波那契数列

斐波那契数列的递归形式会重复计算很多相同的子问题，例如 fib(4) 会递归计算两次 fib(3) 和 fib(2)。通过记忆化搜索，我们可以将中间结果存储起来，从而避免冗余计算。

import java.util.HashMap;
import java.util.Map;
​
public class Fibonacci {private Map<Integer, Integer> memo = new HashMap<>();
​public int fib(int n) {if (n <= 1) return n;if (memo.containsKey(n)) return memo.get(n);  // 从缓存中获取int result = fib(n - 1) + fib(n - 2);memo.put(n, result);  // 将计算结果存入缓存return result;}
​public static void main(String[] args) {Fibonacci fib = new Fibonacci();System.out.println(fib.fib(10));  // 输出 55}
}

这种记忆化搜索通过保存已经计算过的斐波那契值，避免了指数级递归的时间开销，优化后的时间复杂度为 O(n)。

2. 记忆化搜索与动态规划的关系

记忆化搜索可以看作是递归版本的动态规划，它们的核心思想都是缓存中间状态的结果，但在实现方式上有所不同：

• 动态规划（DP）：自底向上，通过填表方式迭代求解。

• 记忆化搜索：自顶向下，通过递归求解的同时缓存结果。

2.1 选择记忆化搜索的场景

• 递归结构清晰的场景：如果问题本质上是递归求解的，且递归结构容易表达，记忆化搜索往往是更直接的解决方法。

• 状态空间较大且需要缓存中间结果：记忆化搜索常用于那些状态多、空间大的问题，尤其适合结合状态压缩技术。

3. 状态压缩与记忆化搜索的结合

3.1 什么是状态压缩？

状态压缩的核心思想是将多个状态变量组合成一个数值或位掩码，以减少存储空间。例如，在图论问题中，可以用一个整数的二进制形式记录多个顶点的访问情况。这种方法通过紧凑的状态表示优化了存储效率，常用于处理复杂的动态规划问题。

3.2 状态压缩的应用场景

状态压缩与记忆化搜索的结合，能够解决很多复杂的图论和动态规划问题：

• TSP 问题（旅行商问题）：通过状态压缩记录已访问的城市，减少重复计算。

• 棋盘覆盖问题：通过压缩棋盘状态，记录当前状态下的覆盖情况。

3.3 示例：TSP 问题中的状态压缩与记忆化搜索

旅行商问题要求找到一个最短路径，使得从起点经过每个城市恰好一次并回到起点。为了优化计算，我们使用状态压缩记录哪些城市已经访问过，并结合记忆化搜索来减少重复计算。

import java.util.Arrays;
​
public class TSP {private int n;private int[][] dist;private int[][] dp;  // dp[state][i] 表示从起点经过 state 状态下到达 i 的最短路径
​public TSP(int n, int[][] dist) {this.n = n;this.dist = dist;this.dp = new int[1 << n][n];  // 状态压缩for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE);dp[1][0] = 0;  // 起点到自身的距离为 0}
​public int solve() {for (int state = 1; state < (1 << n); state++) {for (int last = 0; last < n; last++) {if ((state & (1 << last)) == 0) continue;  // last 必须在当前状态中for (int prev = 0; prev < n; prev++) {if ((state & (1 << prev)) == 0) continue;  // prev 必须在当前状态中dp[state][last] = Math.min(dp[state][last], dp[state ^ (1 << last)][prev] + dist[prev][last]);}}}// 返回经过所有城市并回到起点的最短路径return Arrays.stream(dp[(1 << n) - 1]).min().getAsInt();}
​public static void main(String[] args) {int[][] dist = {{0, 10, 15, 20},{10, 0, 35, 25},{15, 35, 0, 30},{20, 25, 30, 0}};TSP tsp = new TSP(4, dist);System.out.println(tsp.solve());  // 输出 80}
}

在此代码中，我们使用位运算表示哪些城市已经被访问，并结合记忆化搜索记录每个状态下的最短路径，从而避免重复计算。

4. 实战案例：棋盘覆盖问题

4.1 问题描述

给定一个 N×M 的棋盘，要求将其分割成若干个 1×2 的长方形，问有多少种合法的分割方案。

例如当 N=2，M=4N=2，M=4 时，共有 55 种方案。当 N=2，M=3N=2，M=3 时，共有 33 种方案。

如下图所示：

4.2 记忆化搜索与状态压缩的结合

在棋盘覆盖问题中，我们使用位运算来表示每一列的状态，通过记忆化搜索来缓存中间状态，避免重复计算。状态转移则通过位运算来完成。

import java.util.*;public class Main{public static void main(String[] args) {Scanner sca = new Scanner(System.in);int N = 12, M = 1 << N;long[][] f = new long[N][M];int[][] state = new int[M][M];boolean[] st = new boolean[M];while (true) {int n = sca.nextInt();int m = sca.nextInt();//当 n 和 m 同时为 0 结束循环if (n == 0 && m == 0) {break;}for (int i = 0; i < 1<< n; i ++ ) {int cnt = 0;    //  表示的是当前 前面0的个数boolean flag = true;for (int j = 0; j < n; j ++ ) { // 从上倒下判断有多少个0// 判断现在这位是不是 1if ((i >> j & 1) == 1 ) {//如果是1，判断1前面0的个数是不是偶数，奇数的话就结束if ((cnt & 1) == 1) { // & 1  等于 1 就是奇数，反之是偶数flag = false;break;}cnt = 0;} else {cnt++; // 如果当前不是1 ，则 0 的个数 +1}}// 最后还要判断一下最后一层0的个数是不是奇数if ((cnt & 1) == 1) flag = false;// 最后将这一种状态存入st数组，表示true 合法 或者false非法st[i] = flag;}// 这是 i- 1 到 i列的方块for (int i = 0; i < 1 << n; i ++ ) {// 将所有的状态清零，因为多组数据防止上一组的影响Arrays.fill(state[i], 0); for(int j = 0; j < 1 << n; j ++ ) {// 当满足 1. i 和 j没有相交（同一行的两列不能连续放置方块会重叠）//        2. i - 1 列的空格数是不是偶数if ((i & j) == 0 && st[i | j]) {state[i][j] = 1;}}}for (int i = 0; i < N; i ++ ) {// 因为有多组数据，防止上一组数据的干扰Arrays.fill(f[i], 0);}// 边界，横着在第一列方只有一种方案就是 什么也不放 f[0][0] = 1;// 最后的 DP部分//为什么从1开始呢，因为从0开始的话，我们定义的f[m][j]就是前i - 1列已经摆好//如果是0开始，就会从-1个开始摆好，因为我们没有-1列，所以从1开始for (int i = 1; i <= m ; i ++ ) {// 枚举 i - 1 到 i 的所有方案啊for (int j = 0; j < 1 << n; j ++) {//枚举 i- 2 到 i- 1 的所有方案啊for (int k = 0; k < 1 << n; k ++ ) {// 现在的方案等于前面每种k方案的总和if (state[j][k] == 1 ) {f[i][j] += f[i - 1][k];}}}}System.out.println(f[m][0]);}}
}

详细题解请移步：蒙德里安的梦想

通过状态压缩，我们减少了空间消耗，并利用记忆化搜索提升了算法效率。

5. 性能分析与优化策略

5.1 时间与空间复杂度分析

记忆化搜索通过缓存结果，将递归问题的时间复杂度从指数级降低到线性级别；结合状态压缩后，还可以进一步减少空间消耗。在 TSP 问题中，时间复杂度为 O(n^2 * 2^n)，空间复杂度也被压缩到 O(n * 2^n)。

5.2 常见的优化策略

• 剪枝：通过提前判断某些路径不可能达到最优解，避免无效计算。

• 缓存状态：在动态规划中合理设计状态表示，确保状态能够准确地反映问题的当前进展，避免遗漏和重复。

6. 常见的位运算技巧

6.1 设置与检查位

• 设置位：state |= (1 << i) 将第 i 位设为 1。

• 检查位：(state >> i) & 1 检查第 i 位是否为 1。

• 清除位：state &= ~(1 << i) 将第 i 位设为 0。

6.2 示例：动态规划中的位运算

位运算在很多图论问题和动态规划问题中都非常高效。通过对状态进行位操作，可以快速地进行状态转换和检查。

6.2.1问题描述

给定一张 n 个点的带权无向图，点从 0∼n−1 标号，求起点 0 到终点 n−1 的最短 Hamilton 路径。

Hamilton 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次。

import java.util.*;
public class Main{public static void main(String[] args){Scanner scan = new Scanner(System.in);int N = 20, M = 1 << N;int[][] f = new int[M][N]; // f[state][j]: state状态下最后到达点j的最短路径int[][] w = new int[N][N]; // 权重矩阵 w[i][j]: 点i到点j的距离int n = scan.nextInt(); // 点的个数// 读取图的邻接矩阵for(int i = 0 ; i < n ; i ++ )for(int j = 0 ; j < n ; j ++ )w[i][j] = scan.nextInt(); // 初始化动态规划数组，设置为正无穷for(int i = 0 ; i < 1 << n ; i ++ )Arrays.fill(f[i],0x3f3f3f); f[1][0] = 0; // 起点是顶点0，状态为只访问了顶点0// 枚举所有的状态for(int state = 0 ; state < 1 << n ; state ++ ){for(int j = 0 ; j < n ; j ++ ){// 判断当前状态下是否访问过顶点 jif((state >> j & 1) == 1){ for(int k = 0 ; k < n ; k ++ ){// 判断倒数第二步是否访问过顶点 kif((state - (1 << j) >> k & 1) == 1){// 状态转移f[state][j] = Math.min(f[state][j], f[state - (1 << j)][k] + w[k][j]);}}}}}// 输出最终结果，表示从顶点0开始访问所有顶点到终点n-1的最短路径System.out.println(f[(1 << n) - 1][n - 1]);}
}

 详细题解请移步：最短Hamilton路径

7. 总结与扩展

记忆化搜索结合状态压缩是一种极为高效的优化技术，特别是在解决具有重叠子问题和复杂状态空间的问题时，能够显著提升算法的时间和空间效率。在实际应用中，合理地设计状态表示并结合位运算，可以进一步优化问题的求解过程。