动态规划法

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class DynamicProgrammingExamples {

    // 1. 斐波那契数列：自顶向下（记忆化递归）
    public static int fibonacciMemoization(int n) {
        if (n <= 0) return 0;
        // 使用HashMap存储已计算的结果
        Map<Integer, Integer> memo = new HashMap<>();
        return fibonacciRecursive(n, memo);
    }
    
    private static int fibonacciRecursive(int n, Map<Integer, Integer> memo) {
        // 基本情况
        if (n == 1 || n == 2) return 1;
        
        // 如果已计算，直接返回
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        
        // 递归计算并存储结果
        int result = fibonacciRecursive(n - 1, memo) + fibonacciRecursive(n - 2, memo);
        memo.put(n, result);
        return result;
    }
    
    // 2. 斐波那契数列：自底向上（迭代实现）
    public static int fibonacciIterative(int n) {
        if (n <= 0) return 0;
        if (n == 1 || n == 2) return 1;
        
        // 只保存前两个值，优化空间复杂度
        int prevPrev = 1; // f(n-2)
        int prev = 1;     // f(n-1)
        int current = 0;  // f(n)
        
        for (int i = 3; i <= n; i++) {
            current = prev + prevPrev;
            prevPrev = prev;
            prev = current;
        }
        
        return current;
    }
    
    // 3. 0-1背包问题：标准实现
    public static int knapsackStandard(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        if (n == 0 || capacity <= 0) return 0;
        
        // dp[i][j] 表示前i个物品在容量j下的最大价值
        int[][] dp = new int[n + 1][capacity + 1];
        
        // 填充dp表
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= capacity; j++) {
                // 如果当前物品重量超过容量，不放入
                if (weights[i - 1] > j) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    // 选择放入或不放入的最大值
                    dp[i][j] = Math.max(
                        dp[i - 1][j],  // 不放入当前物品
                        values[i - 1] + dp[i - 1][j - weights[i - 1]]  // 放入当前物品
                    );
                }
            }
        }
        
        return dp[n][capacity];
    }
    
    // 4. 0-1背包问题：空间优化实现（滚动数组）
    public static int knapsackOptimized(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        if (n == 0 || capacity <= 0) return 0;
        
        // 只使用一维数组，空间复杂度从O(n*capacity)降至O(capacity)
        int[] dp = new int[capacity + 1];
        
        // 填充dp数组
        for (int i = 0; i < n; i++) {
            // 逆序遍历，避免覆盖需要使用的上一轮数据
            for (int j = capacity; j >= weights[i]; j--) {
                dp[j] = Math.max(dp[j], values[i] + dp[j - weights[i]]);
            }
        }
        
        return dp[capacity];
    }
    
    // 5. 最长公共子序列（LCS）：优化空间实现
    public static int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        
        // 确保使用较短的字符串作为列，进一步节省空间
        if (m < n) {
            return longestCommonSubsequence(text2, text1);
        }
        
        // 只使用两行数组，空间复杂度从O(m*n)降至O(min(m,n))
        int[] prev = new int[n + 1];
        int[] curr = new int[n + 1];
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    curr[j] = prev[j - 1] + 1;
                } else {
                    curr[j] = Math.max(prev[j], curr[j - 1]);
                }
            }
            // 交换两行
            int[] temp = prev;
            prev = curr;
            curr = temp;
            Arrays.fill(curr, 0);
        }
        
        return prev[n];
    }
    
    // 6. 最长递增子序列（LIS）：O(n log n)优化实现
    public static int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        
        // tails[i]表示长度为i+1的LIS的最小尾元素
        int[] tails = new int[nums.length];
        int length = 0;
        
        for (int num : nums) {
            // 二分查找当前元素在tails中的位置
            int left = 0, right = length;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (tails[mid] < num) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            
            // 替换或扩展tails数组
            tails[left] = num;
            if (left == length) {
                length++;
            }
        }
        
        return length;
    }
    
    // 测试
    public static void main(String[] args) {
        // 测试斐波那契数列
        int n = 10;
        System.out.println("斐波那契数列第" + n + "项（记忆化）: " + fibonacciMemoization(n));
        System.out.println("斐波那契数列第" + n + "项（迭代）: " + fibonacciIterative(n));
        
        // 测试0-1背包问题
        int[] weights = {2, 3, 4, 5};
        int[] values = {3, 4, 5, 6};
        int capacity = 5;
        System.out.println("0-1背包最大价值（标准）: " + knapsackStandard(weights, values, capacity));
        System.out.println("0-1背包最大价值（优化）: " + knapsackOptimized(weights, values, capacity));
        
        // 测试最长公共子序列
        String text1 = "abcde", text2 = "ace";
        System.out.println("最长公共子序列长度: " + longestCommonSubsequence(text1, text2));
        
        // 测试最长递增子序列
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println("最长递增子序列长度: " + lengthOfLIS(nums));
    }
}