一、動態規劃

• 核心思想：將復雜問題分解為相互重疊的子問題，通過保存子問題的解來避免重復計算（記憶化）。

動態規劃需要通過子問題的最優解，推導出最終問題的最優解，因此這種方法特別注重子問題之間的轉移關系。我們通常把這些子問題之間的轉移稱為狀態轉移，并把用于刻畫這些狀態轉移的表達式稱為狀態轉移方程。

• 問題結構：必須滿足?最優子結構?和?重疊子問題?兩個性質

• 重疊子問題：

  • 定義：在遞歸求解問題時，子問題并不是新的，而是會被反復計算多次。

  • 動態規劃的做法：將每個子問題的解存儲在一個表格（通常是數組）中，需要時直接查表，用空間換時間。

  • 例子：計算斐波那契數列?F(5)?需要計算?F(4)?和?F(3)，而計算?F(4)?又需要計算?F(3)?和?F(2)。F(3)?被重復計算了。

• 動態規劃解題步驟：

  • 定義狀態：確定dp數組以及下標的含義

  • 確定狀態轉移方程：找出狀態之間的關系式

  • 初始化：確定初始條件

  • 確定遍歷順序：從前向后、從后向前或其他

  • 舉例推導：驗證狀態轉移方程的正確性

1.1?斐波那契數列

public class Fibonacci {// 遞歸解法（非動態規劃，效率低）public static int fibRecursive(int n) {if (n <= 1) return n;return fibRecursive(n - 1) + fibRecursive(n - 2);}// 動態規劃解法 - 自底向上public static int fibDP(int n) {if (n <= 1) return n;int[] dp = new int[n + 1];dp[0] = 0;dp[1] = 1;for (int i = 2; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}// 動態規劃解法 - 空間優化public static int fibDPOptimized(int n) {if (n <= 1) return n;int prev2 = 0, prev1 = 1;for (int i = 2; i <= n; i++) {int current = prev1 + prev2;prev2 = prev1;prev1 = current;}return prev1;}public static void main(String[] args) {int n = 10;System.out.println("斐波那契數列第" + n + "項:");System.out.println("遞歸解法: " + fibRecursive(n));System.out.println("DP解法: " + fibDP(n));System.out.println("DP空間優化解法: " + fibDPOptimized(n));}
}

1.2 0-1背包問題

給定一組物品，每種物品都有自己的重量和價值，在限定的總重量內，如何選擇才能使得物品的總價值最高。

import java.util.ArrayList;
import java.util.List;public class KnapsackWithSolution {/*** 解決0-1背包問題并返回選擇的物品* @param capacity 背包容量* @param weights 物品重量數組* @param values 物品價值數組* @return 包含最大價值和選擇方案的Result對象*/public static Result knapSack(int capacity, int[] weights, int[] values) {int n = weights.length;// 創建動態規劃表int[][] dp = new int[n + 1][capacity + 1];// 填充動態規劃表for (int i = 0; i <= n; i++) {for (int w = 0; w <= capacity; w++) {if (i == 0 || w == 0) {dp[i][w] = 0;} else if (weights[i - 1] <= w) {dp[i][w] = Math.max(values[i - 1] + dp[i - 1][w - weights[i - 1]],dp[i - 1][w]);} else {dp[i][w] = dp[i - 1][w];}}}// 回溯找出選擇的物品List<Integer> selectedItems = new ArrayList<>();int w = capacity;for (int i = n; i > 0 && w > 0; i--) {if (dp[i][w] != dp[i - 1][w]) {selectedItems.add(i - 1); // 添加物品索引（從0開始）w -= weights[i - 1];}}return new Result(dp[n][capacity], selectedItems);}// 結果類，包含最大價值和選擇的物品索引static class Result {int maxValue;List<Integer> selectedItems;public Result(int maxValue, List<Integer> selectedItems) {this.maxValue = maxValue;this.selectedItems = selectedItems;}}public static void main(String[] args) {int[] values = {60, 100, 120, 80, 150};int[] weights = {10, 20, 30, 15, 25};int capacity = 50;Result result = knapSack(capacity, weights, values);System.out.println("背包容量: " + capacity);System.out.println("物品價值: " + java.util.Arrays.toString(values));System.out.println("物品重量: " + java.util.Arrays.toString(weights));System.out.println("最大價值: " + result.maxValue);System.out.println("選擇的物品索引: " + result.selectedItems);// 輸出詳細信息System.out.println("\n選擇的物品詳情:");int totalWeight = 0;int totalValue = 0;for (int index : result.selectedItems) {System.out.println("物品" + index + ": 價值=" + values[index] + ", 重量=" + weights[index]);totalWeight += weights[index];totalValue += values[index];}System.out.println("總重量: " + totalWeight + "/" + capacity);System.out.println("總價值: " + totalValue);}
}

1.3 完全背包問題

與0-1背包問題不同，完全背包允許每種物品被選取多次。

import java.util.Arrays;public class UnboundedKnapsack {/*** 完全背包問題解決方案* @param capacity 背包容量* @param weights 物品重量數組* @param values 物品價值數組* @return 背包能裝的最大價值*/public static int unboundedKnapsack(int capacity, int[] weights, int[] values) {int n = weights.length;// dp[i] 表示容量為i的背包能裝的最大價值int[] dp = new int[capacity + 1];// 初始化dp數組for (int i = 0; i <= capacity; i++) {for (int j = 0; j < n; j++) {if (weights[j] <= i) {dp[i] = Math.max(dp[i], dp[i - weights[j]] + values[j]);}}}return dp[capacity];}/*** 帶有路徑追蹤的完全背包解決方案* @param capacity 背包容量* @param weights 物品重量數組* @param values 物品價值數組*/public static void unboundedKnapsackWithPath(int capacity, int[] weights, int[] values) {int n = weights.length;int[] dp = new int[capacity + 1];int[] selected = new int[capacity + 1]; // 記錄最后選擇的物品// 初始化dp數組和selected數組Arrays.fill(selected, -1);for (int i = 0; i <= capacity; i++) {for (int j = 0; j < n; j++) {if (weights[j] <= i) {if (dp[i] < dp[i - weights[j]] + values[j]) {dp[i] = dp[i - weights[j]] + values[j];selected[i] = j;}}}}// 輸出結果System.out.println("最大價值: " + dp[capacity]);// 回溯找出選擇的物品System.out.print("選擇的物品: ");int remaining = capacity;int[] count = new int[n];while (remaining > 0 && selected[remaining] != -1) {int item = selected[remaining];count[item]++;remaining -= weights[item];}for (int i = 0; i < n; i++) {if (count[i] > 0) {System.out.print("物品" + i + "×" + count[i] + " ");}}System.out.println();// 可視化dp表System.out.println("\nDP表:");System.out.print("容量: ");for (int i = 0; i <= capacity; i++) {System.out.printf("%3d", i);}System.out.print("\n價值: ");for (int i = 0; i <= capacity; i++) {System.out.printf("%3d", dp[i]);}System.out.println();}public static void main(String[] args) {// 示例數據int capacity = 10;int[] weights = {2, 3, 4, 5};int[] values = {3, 4, 5, 6};System.out.println("背包容量: " + capacity);System.out.print("物品重量: ");for (int w : weights) System.out.print(w + " ");System.out.print("\n物品價值: ");for (int v : values) System.out.print(v + " ");System.out.println("\n");// 計算并輸出結果unboundedKnapsackWithPath(capacity, weights, values);// 性能測試System.out.println("\n性能測試:");long startTime = System.nanoTime();int result = unboundedKnapsack(capacity, weights, values);long endTime = System.nanoTime();System.out.println("計算耗時: " + (endTime - startTime) + " 納秒");}
}

1.4 最長公共子序列(LCS)

找到兩個序列的最長公共子序列（不要求連續）。

public class LongestCommonSubsequence {/*** 計算兩個字符串的最長公共子序列長度* @param text1 第一個字符串* @param text2 第二個字符串* @return 最長公共子序列的長度*/public static int lcsLength(String text1, String text2) {int m = text1.length();int n = text2.length();// 創建DP表，dp[i][j]表示text1[0..i-1]和text2[0..j-1]的LCS長度int[][] dp = new int[m + 1][n + 1];// 填充DP表for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (text1.charAt(i - 1) == text2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);}}}return dp[m][n];}/*** 重建最長公共子序列字符串* @param text1 第一個字符串* @param text2 第二個字符串* @return 最長公共子序列字符串*/public static String lcsString(String text1, String text2) {int m = text1.length();int n = text2.length();// 創建DP表int[][] dp = new int[m + 1][n + 1];// 填充DP表for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (text1.charAt(i - 1) == text2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);}}}// 回溯重建LCS字符串return buildLCS(text1, text2, dp, m, n);}/*** 通過回溯DP表重建LCS字符串*/private static String buildLCS(String text1, String text2, int[][] dp, int i, int j) {if (i == 0 || j == 0) {return "";}if (text1.charAt(i - 1) == text2.charAt(j - 1)) {return buildLCS(text1, text2, dp, i - 1, j - 1) + text1.charAt(i - 1);} else if (dp[i - 1][j] > dp[i][j - 1]) {return buildLCS(text1, text2, dp, i - 1, j);} else {return buildLCS(text1, text2, dp, i, j - 1);}}/*** 迭代方式重建LCS字符串（避免遞歸棧溢出）*/public static String lcsStringIterative(String text1, String text2) {int m = text1.length();int n = text2.length();// 創建DP表int[][] dp = new int[m + 1][n + 1];// 填充DP表for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (text1.charAt(i - 1) == text2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);}}}// 迭代回溯重建LCS字符串StringBuilder lcs = new StringBuilder();int i = m, j = n;while (i > 0 && j > 0) {if (text1.charAt(i - 1) == text2.charAt(j - 1)) {lcs.insert(0, text1.charAt(i - 1));i--;j--;} else if (dp[i - 1][j] > dp[i][j - 1]) {i--;} else {j--;}}return lcs.toString();}/*** 打印DP表（用于調試和理解）*/public static void printDPTable(String text1, String text2) {int m = text1.length();int n = text2.length();int[][] dp = new int[m + 1][n + 1];// 填充DP表for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (text1.charAt(i - 1) == text2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);}}}// 打印表頭System.out.print("    ");for (int j = 0; j < n; j++) {System.out.print(text2.charAt(j) + " ");}System.out.println();// 打印DP表for (int i = 0; i <= m; i++) {if (i > 0) {System.out.print(text1.charAt(i - 1) + " ");} else {System.out.print("  ");}for (int j = 0; j <= n; j++) {System.out.print(dp[i][j] + " ");}System.out.println();}}public static void main(String[] args) {String text1 = "ABCDGH";String text2 = "AEDFHR";System.out.println("字符串1: " + text1);System.out.println("字符串2: " + text2);int length = lcsLength(text1, text2);System.out.println("最長公共子序列長度: " + length);String lcsRecursive = lcsString(text1, text2);System.out.println("最長公共子序列(遞歸): " + lcsRecursive);String lcsIterative = lcsStringIterative(text1, text2);System.out.println("最長公共子序列(迭代): " + lcsIterative);System.out.println("\nDP表:");printDPTable(text1, text2);// 更多測試用例System.out.println("\n更多測試用例:");String[][] testCases = {{"AGGTAB", "GXTXAYB", "GTAB"},{"ABCBDAB", "BDCAB", "BCAB"},{"XMJYAUZ", "MZJAWXU", "MJAU"},{"", "ABC", ""},{"ABC", "", ""},{"A", "A", "A"},{"A", "B", ""}};for (String[] testCase : testCases) {String s1 = testCase[0];String s2 = testCase[1];String expected = testCase[2];String result = lcsStringIterative(s1, s2);System.out.printf("'%s' 和 '%s' -> '%s' (預期: '%s') %s\n", s1, s2, result, expected, result.equals(expected) ? "?" : "?");}}
}

1.5 最長遞增子序列(LIS)

目標是找到給定序列中最長的子序列，使得這個子序列的元素按嚴格遞增順序排列。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;public class LongestIncreasingSubsequence {/*** 動態規劃方法求解最長遞增子序列長度* 時間復雜度: O(n^2)* 空間復雜度: O(n)* @param nums 輸入序列* @return 最長遞增子序列的長度*/public static int lengthOfLIS(int[] nums) {if (nums == null || nums.length == 0) {return 0;}int n = nums.length;int[] dp = new int[n]; // dp[i] 表示以nums[i]結尾的最長遞增子序列長度Arrays.fill(dp, 1); // 每個元素本身至少是一個長度為1的遞增子序列int maxLength = 1;for (int i = 1; i < n; i++) {for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) {dp[i] = Math.max(dp[i], dp[j] + 1);}}maxLength = Math.max(maxLength, dp[i]);}return maxLength;}/*** 動態規劃方法求解最長遞增子序列本身* @param nums 輸入序列* @return 最長遞增子序列*/public static List<Integer> findLIS(int[] nums) {if (nums == null || nums.length == 0) {return new ArrayList<>();}int n = nums.length;int[] dp = new int[n]; // dp[i] 表示以nums[i]結尾的最長遞增子序列長度int[] prev = new int[n]; // prev[i] 記錄前驅元素索引，用于重建序列Arrays.fill(dp, 1);Arrays.fill(prev, -1);int maxLength = 1;int endIndex = 0;for (int i = 1; i < n; i++) {for (int j = 0; j < i; j++) {if (nums[i] > nums[j] && dp[i] < dp[j] + 1) {dp[i] = dp[j] + 1;prev[i] = j;}}if (dp[i] > maxLength) {maxLength = dp[i];endIndex = i;}}// 重建最長遞增子序列List<Integer> lis = new ArrayList<>();while (endIndex != -1) {lis.add(0, nums[endIndex]);endIndex = prev[endIndex];}return lis;}/*** 二分查找優化方法求解最長遞增子序列長度* 時間復雜度: O(n log n)* 空間復雜度: O(n)* @param nums 輸入序列* @return 最長遞增子序列的長度*/public static int lengthOfLISBinary(int[] nums) {if (nums == null || nums.length == 0) {return 0;}int n = nums.length;int[] tails = new int[n]; // tails[i] 存儲長度為i+1的遞增子序列的最小末尾元素int len = 0; // 當前最長遞增子序列的長度for (int num : nums) {// 使用二分查找在tails中找到第一個大于等于num的元素位置int left = 0, right = len;while (left < right) {int mid = left + (right - left) / 2;if (tails[mid] < num) {left = mid + 1;} else {right = mid;}}tails[left] = num;if (left == len) {len++;}}return len;}/*** 可視化展示算法執行過程* @param nums 輸入序列*/public static void visualizeLIS(int[] nums) {System.out.println("輸入序列: " + Arrays.toString(nums));// 使用動態規劃方法List<Integer> lis = findLIS(nums);System.out.println("最長遞增子序列: " + lis);System.out.println("長度: " + lis.size());// 展示DP表System.out.println("\n動態規劃表:");int n = nums.length;int[] dp = new int[n];Arrays.fill(dp, 1);System.out.print("索引: ");for (int i = 0; i < n; i++) {System.out.printf("%4d", i);}System.out.print("\n數值: ");for (int num : nums) {System.out.printf("%4d", num);}System.out.print("\nDP值: ");for (int i = 0; i < n; i++) {for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) {dp[i] = Math.max(dp[i], dp[j] + 1);}}System.out.printf("%4d", dp[i]);}System.out.println();// 使用二分查找方法int length = lengthOfLISBinary(nums);System.out.println("二分查找方法得到的最長遞增子序列長度: " + length);}public static void main(String[] args) {// 測試用例int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};visualizeLIS(nums);System.out.println("\n" + "=".repeat(50) + "\n");// 另一個測試用例int[] nums2 = {0, 1, 0, 3, 2, 3};visualizeLIS(nums2);System.out.println("\n" + "=".repeat(50) + "\n");// 性能比較int[] largeNums = new int[1000];for (int i = 0; i < largeNums.length; i++) {largeNums[i] = (int) (Math.random() * 1000);}long startTime = System.nanoTime();int result1 = lengthOfLIS(largeNums);long endTime = System.nanoTime();System.out.println("動態規劃方法耗時: " + (endTime - startTime) + " 納秒");startTime = System.nanoTime();int result2 = lengthOfLISBinary(largeNums);endTime = System.nanoTime();System.out.println("二分查找方法耗時: " + (endTime - startTime) + " 納秒");System.out.println("兩種方法結果是否一致: " + (result1 == result2));}
}

1.6 硬幣找零問題

給定不同面額的硬幣和一個總金額，計算可以湊成總金額所需的最少硬幣個數。

import java.util.Arrays;public class CoinChange {public static int coinChange(int[] coins, int amount) {int[] dp = new int[amount + 1];Arrays.fill(dp, amount + 1);dp[0] = 0;for (int i = 1; i <= amount; i++) {for (int coin : coins) {if (coin <= i) {dp[i] = Math.min(dp[i], dp[i - coin] + 1);}}}return dp[amount] > amount ? -1 : dp[amount];}public static void main(String[] args) {int[] coins = {1, 2, 5};int amount = 11;System.out.println("最少硬幣數: " + coinChange(coins, amount));}
}

1.7?編輯距離

計算將一個字符串轉換成另一個字符串所需的最少操作次數（插入、刪除、替換）。

public class EditDistance {public static int minDistance(String word1, String word2) {int m = word1.length();int n = word2.length();int[][] dp = new int[m + 1][n + 1];for (int i = 0; i <= m; i++) {for (int j = 0; j <= n; j++) {if (i == 0) {dp[i][j] = j;} else if (j == 0) {dp[i][j] = i;} else if (word1.charAt(i - 1) == word2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1];} else {dp[i][j] = 1 + Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]),dp[i - 1][j - 1]);}}}return dp[m][n];}public static void main(String[] args) {String word1 = "horse";String word2 = "ros";System.out.println("編輯距離: " + minDistance(word1, word2));}
}

1.8 正則表達式匹配

import java.util.ArrayList;
import java.util.List;public class RegexMatcher {/*** 正則表達式匹配算法* 支持 '.' 匹配任意單個字符* 支持 '*' 匹配零個或多個前面的元素* @param s 輸入字符串* @param p 正則表達式模式* @return 是否匹配*/public static boolean isMatch(String s, String p) {// 使用動態規劃int m = s.length();int n = p.length();// dp[i][j] 表示s的前i個字符和p的前j個字符是否匹配boolean[][] dp = new boolean[m + 1][n + 1];dp[0][0] = true; // 空字符串和空模式匹配// 處理模式開頭可能有*的情況（如a*可以匹配空字符串）for (int j = 1; j <= n; j++) {if (p.charAt(j - 1) == '*') {dp[0][j] = dp[0][j - 2];}}// 填充dp表for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {char sc = s.charAt(i - 1);char pc = p.charAt(j - 1);if (pc == '.' || pc == sc) {// 當前字符匹配dp[i][j] = dp[i - 1][j - 1];} else if (pc == '*') {// 處理*通配符char prev = p.charAt(j - 2);if (prev == '.' || prev == sc) {// 匹配一個或多個字符dp[i][j] = dp[i][j - 2] || dp[i - 1][j];} else {// 匹配零個字符dp[i][j] = dp[i][j - 2];}}}}return dp[m][n];}/*** 可視化匹配過程* @param s 輸入字符串* @param p 正則表達式模式*/public static void visualizeMatch(String s, String p) {System.out.println("字符串: \"" + s + "\"");System.out.println("模式: \"" + p + "\"");boolean result = isMatchWithVisualization(s, p);System.out.println("匹配結果: " + result);System.out.println();}/*** 帶有可視化輸出的匹配算法* @param s 輸入字符串* @param p 正則表達式模式* @return 是否匹配*/public static boolean isMatchWithVisualization(String s, String p) {int m = s.length();int n = p.length();boolean[][] dp = new boolean[m + 1][n + 1];dp[0][0] = true;// 初始化第一行for (int j = 1; j <= n; j++) {if (p.charAt(j - 1) == '*') {dp[0][j] = dp[0][j - 2];}}// 打印表頭System.out.print("      ");for (int j = 0; j <= n; j++) {if (j == 0) {System.out.print("ε ");} else {System.out.print(p.charAt(j - 1) + " ");}}System.out.println();// 填充dp表并打印每一行for (int i = 0; i <= m; i++) {// 打印行標簽if (i == 0) {System.out.print("ε ");} else {System.out.print(s.charAt(i - 1) + " ");}for (int j = 0; j <= n; j++) {if (j == 0) {System.out.print("[" + (dp[i][j] ? "T" : "F") + "]");continue;}if (i > 0) {char sc = s.charAt(i - 1);char pc = p.charAt(j - 1);if (pc == '.' || pc == sc) {dp[i][j] = dp[i - 1][j - 1];} else if (pc == '*') {char prev = p.charAt(j - 2);if (prev == '.' || prev == sc) {dp[i][j] = dp[i][j - 2] || dp[i - 1][j];} else {dp[i][j] = dp[i][j - 2];}} else {dp[i][j] = false;}}System.out.print("[" + (dp[i][j] ? "T" : "F") + "]");}System.out.println();}return dp[m][n];}/*** 查找所有匹配的子串* @param s 輸入字符串* @param p 正則表達式模式* @return 所有匹配的子串起始位置列表*/public static List<Integer> findAllMatches(String s, String p) {List<Integer> matches = new ArrayList<>();int n = s.length();int m = p.length();// 嘗試從每個位置開始匹配for (int i = 0; i <= n; i++) {if (isMatchFromIndex(s, p, i, 0)) {matches.add(i);}}return matches;}/*** 從指定位置開始匹配* @param s 輸入字符串* @param p 正則表達式模式* @param sIndex 字符串起始索引* @param pIndex 模式起始索引* @return 是否匹配*/private static boolean isMatchFromIndex(String s, String p, int sIndex, int pIndex) {// 如果模式已經匹配完成if (pIndex >= p.length()) {return sIndex >= s.length();}// 檢查當前字符是否匹配boolean firstMatch = (sIndex < s.length() && (p.charAt(pIndex) == '.' || p.charAt(pIndex) == s.charAt(sIndex)));// 處理*通配符if (pIndex + 1 < p.length() && p.charAt(pIndex + 1) == '*') {return isMatchFromIndex(s, p, sIndex, pIndex + 2) || // 匹配0次(firstMatch && isMatchFromIndex(s, p, sIndex + 1, pIndex)); // 匹配1次或多次} else {return firstMatch && isMatchFromIndex(s, p, sIndex + 1, pIndex + 1);}}public static void main(String[] args) {// 測試用例String[] testCases = {"aa", "a",     // false"aa", "a*",    // true"ab", ".*",    // true"aab", "c*a*b", // true"mississippi", "mis*is*p*.", // false"abc", "a.c",  // true"abcd", "a.*d" // true};System.out.println("正則表達式匹配測試:");System.out.println("==================");for (int i = 0; i < testCases.length; i += 2) {String s = testCases[i];String p = testCases[i + 1];visualizeMatch(s, p);}// 測試查找所有匹配System.out.println("查找所有匹配的子串:");System.out.println("==================");String text = "aababcabcd";String pattern = "a.*b";List<Integer> matches = findAllMatches(text, pattern);System.out.println("文本: \"" + text + "\"");System.out.println("模式: \"" + pattern + "\"");System.out.println("匹配起始位置: " + matches);// 顯示匹配的子串for (int start : matches) {// 找到匹配的結束位置int end = start;while (end < text.length() && isMatchFromIndex(text, pattern, start, end - start + 1)) {end++;}System.out.println("匹配子串: \"" + text.substring(start, end) + "\"");}// 性能測試System.out.println("\n性能測試:");System.out.println("=========");String longText = "a".repeat(100) + "b";String longPattern = "a*b";long startTime = System.nanoTime();boolean result = isMatch(longText, longPattern);long endTime = System.nanoTime();System.out.println("長文本匹配結果: " + result);System.out.println("耗時: " + (endTime - startTime) + " 納秒");}
}

二、貪心算法

• 核心思想：每一步都采取當前狀態下最優的選擇，希望導致全局最優。

• 問題結構：必須滿足?最優子結構?和?貪心選擇性質。

• 貪心選擇性質：

  • 定義：通過做出局部最優選擇，就能達到全局最優解。不需要考慮子問題的解。

  • 簡單說：每一步的貪心選擇都是安全的，不會影響后續決策達到全局最優。

  • 例子：找零錢問題（硬幣無限供應）。要湊出36元，有25元、10元、5元、1元面值的硬幣。貪心策略是：每次都選不超過剩余金額的最大面額硬幣（先拿25，剩余11；再拿10，剩余1；再拿1）。在這種情況下，貪心策略是有效的。

2.1?找零錢問題

給定不同面額的硬幣和一個總金額，計算最少需要多少硬幣來湊成這個金額（假設硬幣數量無限）。

import java.util.Arrays;public class CoinChange {public static int minCoins(int[] coins, int amount) {// 按面額從大到小排序Arrays.sort(coins);int count = 0;int index = coins.length - 1;while (amount > 0 && index >= 0) {if (coins[index] <= amount) {int num = amount / coins[index];count += num;amount -= num * coins[index];}index--;}return amount == 0 ? count : -1;}public static void main(String[] args) {int[] coins = {1, 5, 10, 25};int amount = 63;System.out.println("最少需要硬幣數: " + minCoins(coins, amount));}
}

2.2?區間調度算法

給定一組區間（每個區間有開始時間和結束時間），找到最大的互不重疊的區間子集（即這些區間之間沒有重疊）。

import java.util.*;public class IntervalScheduling {// 區間類static class Interval {int start;int end;String name;public Interval(int start, int end, String name) {this.start = start;this.end = end;this.name = name;}@Overridepublic String toString() {return name + "[" + start + "-" + end + "]";}}/*** 最早開始時間優先策略（非最優）*/public static List<Interval> earliestStartFirst(List<Interval> intervals) {if (intervals == null || intervals.isEmpty()) {return new ArrayList<>();}// 按開始時間排序List<Interval> sorted = new ArrayList<>(intervals);sorted.sort(Comparator.comparingInt(a -> a.start));List<Interval> result = new ArrayList<>();result.add(sorted.get(0));int lastEnd = sorted.get(0).end;for (int i = 1; i < sorted.size(); i++) {Interval current = sorted.get(i);if (current.start >= lastEnd) {result.add(current);lastEnd = current.end;}}return result;}/*** 最短區間優先策略（非最優）*/public static List<Interval> shortestIntervalFirst(List<Interval> intervals) {if (intervals == null || intervals.isEmpty()) {return new ArrayList<>();}// 按區間長度排序List<Interval> sorted = new ArrayList<>(intervals);sorted.sort(Comparator.comparingInt(a -> (a.end - a.start)));List<Interval> result = new ArrayList<>();boolean[] occupied = new boolean[getMaxTime(intervals) + 1];for (Interval interval : sorted) {boolean canAdd = true;// 檢查時間段是否被占用for (int i = interval.start; i < interval.end; i++) {if (occupied[i]) {canAdd = false;break;}}if (canAdd) {result.add(interval);// 標記時間段為占用for (int i = interval.start; i < interval.end; i++) {occupied[i] = true;}}}return result;}/*** 最早結束時間優先策略（最優解）*/public static List<Interval> earliestFinishFirst(List<Interval> intervals) {if (intervals == null || intervals.isEmpty()) {return new ArrayList<>();}// 按結束時間排序List<Interval> sorted = new ArrayList<>(intervals);sorted.sort(Comparator.comparingInt(a -> a.end));List<Interval> result = new ArrayList<>();result.add(sorted.get(0));int lastEnd = sorted.get(0).end;for (int i = 1; i < sorted.size(); i++) {Interval current = sorted.get(i);if (current.start >= lastEnd) {result.add(current);lastEnd = current.end;}}return result;}/*** 獲取所有區間中的最大時間*/private static int getMaxTime(List<Interval> intervals) {int max = 0;for (Interval interval : intervals) {if (interval.end > max) {max = interval.end;}}return max;}/*** 打印調度結果*/public static void printSchedule(String title, List<Interval> schedule) {System.out.println(title + " (" + schedule.size() + "個區間):");for (Interval interval : schedule) {System.out.println("  " + interval);}System.out.println();}/*** 可視化調度結果*/public static void visualizeSchedule(List<Interval> schedule, int maxTime) {System.out.println("調度可視化:");for (Interval interval : schedule) {System.out.printf("%-10s", interval.name);for (int i = 0; i <= maxTime; i++) {if (i >= interval.start && i < interval.end) {System.out.print("■");} else {System.out.print(" ");}}System.out.println();}// 打印時間軸System.out.print("          ");for (int i = 0; i <= maxTime; i++) {System.out.print(i % 10);}System.out.println();}public static void main(String[] args) {// 創建測試區間List<Interval> intervals = Arrays.asList(new Interval(1, 4, "A"),new Interval(3, 5, "B"),new Interval(0, 6, "C"),new Interval(5, 7, "D"),new Interval(3, 8, "E"),new Interval(5, 9, "F"),new Interval(6, 10, "G"),new Interval(8, 11, "H"),new Interval(8, 12, "I"),new Interval(2, 13, "J"),new Interval(12, 14, "K"));System.out.println("所有區間:");for (Interval interval : intervals) {System.out.println("  " + interval);}System.out.println();// 測試不同策略List<Interval> schedule1 = earliestStartFirst(intervals);printSchedule("最早開始時間優先策略", schedule1);List<Interval> schedule2 = shortestIntervalFirst(intervals);printSchedule("最短區間優先策略", schedule2);List<Interval> schedule3 = earliestFinishFirst(intervals);printSchedule("最早結束時間優先策略(最優)", schedule3);// 可視化最優調度int maxTime = getMaxTime(intervals);visualizeSchedule(schedule3, maxTime);// 性能測試System.out.println("\n性能測試:");List<Interval> largeIntervals = generateLargeTest(1000);long startTime = System.currentTimeMillis();List<Interval> result = earliestFinishFirst(largeIntervals);long endTime = System.currentTimeMillis();System.out.println("1000個區間的最優調度計算耗時: " + (endTime - startTime) + "ms");System.out.println("選擇了 " + result.size() + " 個區間");}/*** 生成大規模測試數據*/private static List<Interval> generateLargeTest(int size) {List<Interval> intervals = new ArrayList<>();Random random = new Random();for (int i = 0; i < size; i++) {int start = random.nextInt(1000);int duration = random.nextInt(50) + 1;intervals.add(new Interval(start, start + duration, "T" + i));}return intervals;}
}

2.3 加權區間調度

/*** 加權區間調度（動態規劃解法）*/
public static List<Interval> weightedIntervalScheduling(List<Interval> intervals, int[] weights) {if (intervals == null || intervals.isEmpty()) {return new ArrayList<>();}// 按結束時間排序List<Interval> sorted = new ArrayList<>(intervals);sorted.sort(Comparator.comparingInt(a -> a.end));int n = sorted.size();int[] dp = new int[n + 1];int[] prev = new int[n];// 預處理：找到每個區間之前最近的不重疊區間for (int i = 0; i < n; i++) {prev[i] = -1;for (int j = i - 1; j >= 0; j--) {if (sorted.get(j).end <= sorted.get(i).start) {prev[i] = j;break;}}}// 動態規劃計算最大權重dp[0] = 0;for (int i = 1; i <= n; i++) {int include = weights[i - 1] + (prev[i - 1] >= 0 ? dp[prev[i - 1] + 1] : 0);int exclude = dp[i - 1];dp[i] = Math.max(include, exclude);}// 回溯找出選擇的區間List<Interval> result = new ArrayList<>();int i = n;while (i > 0) {if (dp[i] != dp[i - 1]) {result.add(sorted.get(i - 1));i = prev[i - 1] >= 0 ? prev[i - 1] + 1 : 0;} else {i--;}}Collections.reverse(result);return result;
}

2.4?背包問題（分數背包）

給定物品的重量和價值，選擇物品放入背包，使得總價值最大（物品可以分割）。

import java.util.Arrays;class Item implements Comparable<Item> {int weight;int value;public Item(int weight, int value) {this.weight = weight;this.value = value;}@Overridepublic int compareTo(Item other) {double ratio1 = (double) value / weight;double ratio2 = (double) other.value / other.weight;return Double.compare(ratio2, ratio1); // 按價值比降序排序}
}public class FractionalKnapsack {public static double getMaxValue(Item[] items, int capacity) {Arrays.sort(items);double totalValue = 0;int remainingCapacity = capacity;for (Item item : items) {if (remainingCapacity >= item.weight) {totalValue += item.value;remainingCapacity -= item.weight;} else {double fraction = (double) remainingCapacity / item.weight;totalValue += fraction * item.value;break;}}return totalValue;}public static void main(String[] args) {Item[] items = {new Item(10, 60),new Item(20, 100),new Item(30, 120)};int capacity = 50;System.out.println("最大價值: " + getMaxValue(items, capacity));}
}

2.5?霍夫曼編碼

用于數據壓縮的貪心算法，通過構建最優前綴碼來最小化編碼長度。

import java.util.PriorityQueue;class HuffmanNode implements Comparable<HuffmanNode> {char data;int frequency;HuffmanNode left, right;public HuffmanNode(char data, int frequency) {this.data = data;this.frequency = frequency;left = right = null;}@Overridepublic int compareTo(HuffmanNode other) {return this.frequency - other.frequency;}
}public class HuffmanCoding {public static void printCodes(HuffmanNode root, String code) {if (root == null) return;if (root.left == null && root.right == null) {System.out.println(root.data + ": " + code);return;}printCodes(root.left, code + "0");printCodes(root.right, code + "1");}public static HuffmanNode buildHuffmanTree(char[] chars, int[] freq) {PriorityQueue<HuffmanNode> queue = new PriorityQueue<>();for (int i = 0; i < chars.length; i++) {queue.add(new HuffmanNode(chars[i], freq[i]));}while (queue.size() > 1) {HuffmanNode left = queue.poll();HuffmanNode right = queue.poll();HuffmanNode parent = new HuffmanNode('-', left.frequency + right.frequency);parent.left = left;parent.right = right;queue.add(parent);}return queue.poll();}public static void main(String[] args) {char[] chars = {'a', 'b', 'c', 'd', 'e', 'f'};int[] freq = {5, 9, 12, 13, 16, 45};HuffmanNode root = buildHuffmanTree(chars, freq);printCodes(root, "");}
}

2.6?最小生成樹（Prim算法）

用于在加權無向圖中找到連接所有頂點的最小權重邊集合。

import java.util.Arrays;public class PrimMST {public static void primMST(int[][] graph) {int V = graph.length;int[] parent = new int[V];int[] key = new int[V];boolean[] mstSet = new boolean[V];Arrays.fill(key, Integer.MAX_VALUE);key[0] = 0;parent[0] = -1;for (int count = 0; count < V - 1; count++) {int u = minKey(key, mstSet);mstSet[u] = true;for (int v = 0; v < V; v++) {if (graph[u][v] != 0 && !mstSet[v] && graph[u][v] < key[v]) {parent[v] = u;key[v] = graph[u][v];}}}printMST(parent, graph);}private static int minKey(int[] key, boolean[] mstSet) {int min = Integer.MAX_VALUE;int minIndex = -1;for (int v = 0; v < key.length; v++) {if (!mstSet[v] && key[v] < min) {min = key[v];minIndex = v;}}return minIndex;}private static void printMST(int[] parent, int[][] graph) {System.out.println("邊 \t權重");for (int i = 1; i < graph.length; i++) {System.out.println(parent[i] + " - " + i + "\t" + graph[i][parent[i]]);}}public static void main(String[] args) {int[][] graph = {{0, 2, 0, 6, 0},{2, 0, 3, 8, 5},{0, 3, 0, 0, 7},{6, 8, 0, 0, 9},{0, 5, 7, 9, 0}};primMST(graph);}
}

2.7?分發餅干

問題描述：假設你是一位家長，想要給孩子們分發餅干。每個孩子最多只能給一塊餅干。對于每個孩子?i，有一個胃口值?g[i]，這是能讓孩子滿足的最小餅干尺寸；對于每塊餅干?j，有一個尺寸?s[j]。如果?s[j] >= g[i]，可以將餅干?j?分配給孩子?i，這個孩子會得到滿足。目標是盡可能滿足更多的孩子，并輸出可以滿足的最大孩子數量。

import java.util.Arrays;public class AssignCookies {/*** 分發餅干算法 - 貪心策略* @param g 孩子的胃口數組* @param s 餅干的尺寸數組* @return 可以滿足的最大孩子數量*/public static int findContentChildren(int[] g, int[] s) {// 對兩個數組進行排序Arrays.sort(g);Arrays.sort(s);int childIndex = 0; // 指向當前待滿足的孩子int cookieIndex = 0; // 指向當前可用的餅干// 遍歷餅干和孩子while (childIndex < g.length && cookieIndex < s.length) {// 如果當前餅干可以滿足當前孩子if (s[cookieIndex] >= g[childIndex]) {childIndex++; // 滿足了一個孩子，移動到下一個孩子}cookieIndex++; // 無論是否滿足，都要移動到下一個餅干}return childIndex;}/*** 分發餅干算法 - 另一種實現（從大到小分配）*/public static int findContentChildrenReverse(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int childIndex = g.length - 1; // 從胃口最大的孩子開始int cookieIndex = s.length - 1; // 從最大的餅干開始int count = 0;while (childIndex >= 0 && cookieIndex >= 0) {// 如果當前餅干可以滿足當前孩子if (s[cookieIndex] >= g[childIndex]) {count++; // 滿足了一個孩子cookieIndex--; // 使用了一個餅干}childIndex--; // 無論是否滿足，都移動到下一個孩子}return count;}/*** 詳細版本：輸出分配過程*/public static int findContentChildrenDetailed(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);System.out.println("排序后的孩子胃口: " + Arrays.toString(g));System.out.println("排序后的餅干尺寸: " + Arrays.toString(s));System.out.println();int childIndex = 0;int cookieIndex = 0;int count = 0;while (childIndex < g.length && cookieIndex < s.length) {System.out.println("嘗試用餅干" + cookieIndex + "(尺寸=" + s[cookieIndex] + ")滿足孩子" + childIndex + "(胃口=" + g[childIndex] + ")");if (s[cookieIndex] >= g[childIndex]) {System.out.println("  成功! 孩子" + childIndex + "得到滿足");count++;childIndex++;} else {System.out.println("  失敗! 餅干太小");}cookieIndex++;System.out.println("已滿足孩子數: " + count);System.out.println();}return count;}public static void main(String[] args) {// 測試用例1int[] g1 = {1, 2, 3};int[] s1 = {1, 1};System.out.println("測試用例1:");System.out.println("孩子胃口: " + Arrays.toString(g1));System.out.println("餅干尺寸: " + Arrays.toString(s1));System.out.println("可以滿足的孩子數量: " + findContentChildren(g1, s1));System.out.println();// 測試用例2int[] g2 = {1, 2};int[] s2 = {1, 2, 3};System.out.println("測試用例2:");System.out.println("孩子胃口: " + Arrays.toString(g2));System.out.println("餅干尺寸: " + Arrays.toString(s2));System.out.println("可以滿足的孩子數量: " + findContentChildren(g2, s2));System.out.println();// 測試用例3 - 詳細過程int[] g3 = {3, 1, 2, 4};int[] s3 = {2, 1, 3, 2};System.out.println("測試用例3 - 詳細過程:");System.out.println("可以滿足的孩子數量: " + findContentChildrenDetailed(g3, s3));System.out.println();// 測試用例4 - 從大到小分配int[] g4 = {1, 2, 3, 4, 5};int[] s4 = {1, 3, 3, 4};System.out.println("測試用例4 - 從大到小分配:");System.out.println("孩子胃口: " + Arrays.toString(g4));System.out.println("餅干尺寸: " + Arrays.toString(s4));System.out.println("可以滿足的孩子數量: " + findContentChildrenReverse(g4, s4));System.out.println();// 性能測試System.out.println("性能測試:");int[] g5 = new int[10000];int[] s5 = new int[10000];for (int i = 0; i < 10000; i++) {g5[i] = (int) (Math.random() * 100) + 1;s5[i] = (int) (Math.random() * 100) + 1;}long startTime = System.currentTimeMillis();int result = findContentChildren(g5, s5);long endTime = System.currentTimeMillis();System.out.println("10000個孩子和餅干，可以滿足的孩子數量: " + result);System.out.println("計算耗時: " + (endTime - startTime) + "ms");}
}

三、動態規劃與貪心算法對比

如何選擇：

1. 先看問題是否具有貪心選擇性質。這通常需要證明或憑經驗（經典模型）。如果能用貪心，優先選擇它，因為其效率極高。

   • 試探方法：先嘗試設計一個貪心策略，然后舉反例看看它會不會失敗。如果找不到反例，并且問題很像經典的貪心問題，那么它很可能就用貪心。

2. 如果貪心算法可能失敗，或者問題涉及復雜的決策和狀態，那么毫不猶豫地選擇動態規劃。

   • 思考如何定義狀態（dp數組的含義）。

   • 思考狀態如何轉移（遞推公式）。

   • 思考初始條件和邊界情況。