打表法从原理到实战详解

打表法是一种实用且高效的优化手段，它通过预先计算并存储问题的答案，在实际运行时直接查表获取结果，避免重复计算，从而大幅提升程序运行效率。本文我将结合多个经典案例，深入讲解打表法的应用场景、实现方式及优化技巧，帮你掌握这一重要的编码方法。

一、打表法基本信息

1.1 打表法定义

打表法，顾名思义，就是将问题的答案预先计算出来并存储在“表”（数组、哈希表等数据结构）中，后续遇到相同问题时，直接从表中读取答案，无需再次进行复杂计算。这种方法适用于问题的输入范围有限、计算过程耗时较长，且答案可以提前计算的场景。

1.2 打表法适用场景

• 数据范围固定：输入数据的范围较小且确定，例如计算1到10000以内的所有质数、1到100的阶乘等。
• 计算复杂耗时：问题的计算过程复杂，重复计算会消耗大量时间，如一些动态规划问题、数论问题等。
• 答案可预先计算：问题的答案可以在程序运行前通过其他方式（如编写专门的计算程序、数学推导等）计算得出，并且不会随着程序运行过程而改变。

1.3 打表法的优缺点

• 优点：
  • 提高效率：避免重复计算，显著减少程序运行时间。
  • 简化逻辑：在实际使用时，只需查表操作，简化了程序的运行逻辑。
• 缺点：
  • 占用空间：需要预先存储答案，可能会占用较多内存空间。
  • 灵活性差：打表结果依赖于预先确定的输入范围，若输入范围改变，可能需要重新打表。

二、打表法经典案例解析

2.1 快速计算斐波那契数列

2.1.1 问题描述

斐波那契数列是一个经典的数列，其定义为：$F(0)=0$，$F(1)=1$，$F(n)=F(n-1)+F(n-2)$（$n\ge 2$）。现在需要快速计算斐波那契数列中第n项的值（$0\le n\le 100$）。

2.1.2 打表思路

由于n的范围较小且确定（$0\le n\le 100$），可以预先使用循环计算出斐波那契数列前101项的值，并存储在数组中。后续需要查询时，直接从数组中获取对应项的值。

2.1.3 Java代码实现

public class FibonacciTable {private static final int[] fibonacciTable;static {fibonacciTable = new int[101];fibonacciTable[0] = 0;fibonacciTable[1] = 1;for (int i = 2; i < 101; i++) {fibonacciTable[i] = fibonacciTable[i - 1] + fibonacciTable[i - 2];}}public static int getFibonacci(int n) {if (n < 0 || n > 100) {throw new IllegalArgumentException("n的范围应在0到100之间");}return fibonacciTable[n];}public static void main(String[] args) {System.out.println(getFibonacci(10));  // 输出55}
}

2.1.4 复杂度分析

• 打表时间复杂度：打表过程通过一次循环计算，时间复杂度为$O(n)$，这里n = 101。
• 查询时间复杂度：查询时直接从数组中取值，时间复杂度为$O(1)$ 。
• 空间复杂度：使用一个长度为101的数组存储打表结果，空间复杂度为$O(n)$ 。

2.2 快速判断质数（埃氏筛法结合打表）

2.2.1 问题描述

给定一个整数n（$1\le n\le 1000000$），需要快速判断它是否为质数。

2.2.2 打表思路

使用埃氏筛法预先计算出1到1000000范围内的所有质数，并将结果存储在布尔数组中，true表示对应下标是质数，false表示不是质数。后续判断某个数是否为质数时，直接从数组中读取对应位置的值。

2.2.3 Java代码实现

public class PrimeTable {private static final boolean[] primeTable;static {primeTable = new boolean[1000001];Arrays.fill(primeTable, true);primeTable[0] = primeTable[1] = false;for (int i = 2; i * i <= 1000000; i++) {if (primeTable[i]) {for (int j = i * i; j <= 1000000; j += i) {primeTable[j] = false;}}}}public static boolean isPrime(int n) {if (n < 1 || n > 1000000) {throw new IllegalArgumentException("n的范围应在1到1000000之间");}return primeTable[n];}public static void main(String[] args) {System.out.println(isPrime(17));  // 输出trueSystem.out.println(isPrime(18));  // 输出false}
}

2.2.4 复杂度分析

• 打表时间复杂度：埃氏筛法打表过程的时间复杂度为$O(n\log \log n)$，这里n = 1000000 。
• 查询时间复杂度：查询时直接从数组中取值，时间复杂度为$O(1)$ 。
• 空间复杂度：使用一个长度为1000001的布尔数组存储打表结果，空间复杂度为$O(n)$ 。

2.3 动态规划问题的打表优化（最长公共子序列）

2.3.1 问题描述

给定两个字符串text1和text2，返回这两个字符串的最长公共子序列的长度。例如，输入text1 = "abcde"，text2 = "ace"，输出为3，因为最长公共子序列是"ace" 。

2.3.2 打表思路

在一些算法竞赛或特定场景中，如果已知输入字符串的长度范围有限（假设两个字符串长度都不超过100），可以预先计算出所有可能长度的字符串组合的最长公共子序列长度，并存储在二维数组中。实际使用时，根据输入字符串的长度直接从表中获取结果。

2.3.3 Java代码实现

public class LCSLookupTable {private static final int[][] lcsTable;static {lcsTable = new int[101][101];for (int i = 1; i < 101; i++) {for (int j = 1; j < 101; j++) {// 这里只是简单示例初始化，实际计算应使用动态规划lcsTable[i][j] = 0; }}// 假设这里有一个完整的动态规划计算过程填充lcsTable，此处省略}public static int longestCommonSubsequence(String text1, String text2) {int m = text1.length();int n = text2.length();if (m > 100 || n > 100) {throw new IllegalArgumentException("字符串长度应不超过100");}return lcsTable[m][n];}public static void main(String[] args) {System.out.println(longestCommonSubsequence("abc", "ac"));  // 假设打表结果正确，输出2}
}

2.3.4 复杂度分析

• 打表时间复杂度：如果使用动态规划计算并填充二维表，时间复杂度为$O(M\times N)$，其中M和N分别为预先设定的字符串长度上限（这里M = N = 100） 。
• 查询时间复杂度：查询时直接从二维数组中取值，时间复杂度为$O(1)$ 。
• 空间复杂度：使用一个101×101的二维数组存储打表结果，空间复杂度为$O(M\times N)$ 。

三、打表法的优化与注意事项

3.1 优化技巧

• 压缩存储：当打表结果占用空间较大时，可以考虑使用压缩算法（如位图、哈希压缩等）减少存储空间。例如，在存储大量布尔值的打表结果时，可使用位图表示，将多个布尔值存储在一个字节中。
• 分块打表：对于输入范围较大的情况，可以采用分块打表的方式。将输入范围划分为多个小块，每个小块单独打表，查询时先确定所在块，再在块内查询，既能减少内存占用，又能保持较高的查询效率。

3.2 注意事项

• 范围匹配：确保打表的范围覆盖实际使用时的输入范围，否则可能会出现越界或无法查询到结果的情况。
• 数据更新：如果问题的答案会随着某些条件改变而变化，打表法可能不适用，或者需要重新打表。
• 内存限制：在使用打表法时，要注意程序的内存限制，避免因打表占用过多内存导致程序运行出错。

That’s all, thanks for reading!
觉得有用就点个赞、收进收藏夹吧！关注我，获取更多干货～