打表法是一種實用且高效的優化手段，它通過預先計算并存儲問題的答案，在實際運行時直接查表獲取結果，避免重復計算，從而大幅提升程序運行效率。本文我將結合多個經典案例，深入講解打表法的應用場景、實現方式及優化技巧，幫你掌握這一重要的編碼方法。

一、打表法基本信息

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!
覺得有用就點個贊、收進收藏夾吧！關注我，獲取更多干貨～