基础思想：动态规划与贪心算法

一、动态规划

• 核心思想：将复杂问题分解为相互重叠的子问题，通过保存子问题的解来避免重复计算（记忆化）。

动态规划需要通过子问题的最优解，推导出最终问题的最优解，因此这种方法特别注重子问题之间的转移关系。我们通常把这些子问题之间的转移称为状态转移，并把用于刻画这些状态转移的表达式称为状态转移方程。

• 问题结构：必须满足 最优子结构 和 重叠子问题 两个性质

• 重叠子问题：

  • 定义：在递归求解问题时，子问题并不是新的，而是会被反复计算多次。

  • 动态规划的做法：将每个子问题的解存储在一个表格（通常是数组）中，需要时直接查表，用空间换时间。

  • 例子：计算斐波那契数列 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;
        }
        
        @Override
        public 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;
    }
    
    @Override
    public 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;
    }
    
    @Override
    public 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) {
        // 测试用例1
        int[] 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();
        
        // 测试用例2
        int[] 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数组的含义）。

   • 思考状态如何转移（递推公式）。

   • 思考初始条件和边界情况。