动态规划完整入门教程 (Java版)

目录

  1. 什么是动态规划
  2. 核心概念
  3. 动态规划vs递归vs贪心
  4. 解题步骤
  5. 经典入门问题
  6. 常见问题类型
  7. 优化技巧
  8. 实战练习

什么是动态规划

简单理解

动态规划（Dynamic Programming，简称DP）是一种通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法。

核心思想：把已经解决过的子问题的答案记录下来，当再次遇到相同的子问题时，直接使用已有的答案，避免重复计算。

生活中的例子

想象你在爬楼梯：

  • 要到达第10级台阶，你可以从第9级跨1步，或从第8级跨2步
  • 要到达第9级，你可以从第8级跨1步，或从第7级跨2步
  • …

你会发现，到达每一级的方法数都依赖于前面几级的方法数。如果我们记录下每一级的结果，就不需要重复计算了。

动态规划的特点

  1. 最优子结构：问题的最优解包含子问题的最优解
  2. 重叠子问题：在求解过程中，会反复遇到相同的子问题
  3. 无后效性：当前状态只与之前的状态有关，与未来无关

核心概念

1. 状态 (State)

状态是对问题在某个阶段的描述。

例子：在爬楼梯问题中

  • 状态可以定义为：“到达第 i 级台阶”
  • 用 dp[i] 表示到达第 i 级台阶的方法数

2. 状态转移方程 (State Transfer Equation)

状态转移方程描述了不同状态之间的关系。

例子：爬楼梯

dp[i] = dp[i-1] + dp[i-2]

意思是：到达第i级的方法数 = 从第(i-1)级跨1步 + 从第(i-2)级跨2步

3. 初始状态 (Base Case)

初始状态是递推的起点。

例子：爬楼梯

dp[1] = 1  // 到达第1级只有1种方法
dp[2] = 2  // 到达第2级有2种方法：1+1 或 2

4. 最终答案

通常在 dp 数组的某个位置，或通过遍历 dp 数组得到。

动态规划 vs 递归 vs 贪心

递归（自顶向下）

从大问题开始，不断分解为小问题。

// 递归：效率低，有大量重复计算
int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);  // 重复计算！
}

问题：计算 fib(5) 时，fib(3) 会被计算多次。

记忆化递归（自顶向下 + 缓存）

用数组记录已经计算过的结果。

// 记忆化递归：优化递归
int[] memo;

int fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];  // 已经计算过
    memo[n] = fib(n-1) + fib(n-2);
    return memo[n];
}

动态规划（自底向上）

从最小的子问题开始，逐步推导到大问题。

// 动态规划：从小到大
int fib(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];
}

贪心算法

每一步都做当前看起来最好的选择，不保证全局最优。

区别：

  • 贪心：局部最优，不一定全局最优
  • 动态规划：通过子问题的最优解，得到全局最优解

解题步骤

标准五步法

第1步：确定状态定义

思考：用什么来描述问题的阶段？

例子：爬楼梯

  • dp[i] 表示：到达第 i 级台阶的方法数
第2步：确定状态转移方程

思考：当前状态如何从之前的状态推导出来？

例子：爬楼梯

  • dp[i] = dp[i-1] + dp[i-2]
第3步：确定初始状态

思考：最简单的情况是什么？

例子：爬楼梯

  • dp[1] = 1
  • dp[2] = 2
第4步：确定遍历顺序

思考：应该从小到大还是从大到小遍历？

例子：爬楼梯

  • 从小到大：for (int i = 3; i <= n; i++)
第5步：返回结果

思考：答案在哪里？

例子：爬楼梯

  • return dp[n]

经典入门问题

问题1：斐波那契数列

问题描述

斐波那契数列定义如下：

  • F(0) = 0
  • F(1) = 1
  • F(n) = F(n-1) + F(n-2)，当 n > 1

求第 n 个斐波那契数。

解题分析

1. 状态定义

  • dp[i]：第 i 个斐波那契数

2. 状态转移方程

  • dp[i] = dp[i-1] + dp[i-2]

3. 初始状态

  • dp[0] = 0
  • dp[1] = 1

4. 遍历顺序

  • 从小到大
代码实现
public class Fibonacci {
    
    // 方法1：动态规划（标准）
    public static int fib(int n) {
        // 边界情况
        if (n <= 1) {
            return n;
        }
        
        // 创建dp数组
        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];
    }
    
    // 方法2：空间优化（只需要保存前两个数）
    public static int fibOptimized(int n) {
        if (n <= 1) {
            return n;
        }
        
        int prev2 = 0;  // dp[i-2]
        int prev1 = 1;  // dp[i-1]
        int current = 0;
        
        for (int i = 2; i <= n; i++) {
            current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }
        
        return current;
    }
    
    // 测试
    public static void main(String[] args) {
        System.out.println("F(10) = " + fib(10));  // 55
        System.out.println("F(10) = " + fibOptimized(10));  // 55
    }
}

时间复杂度：O(n)
空间复杂度：O(n) → 优化后 O(1)

问题2：爬楼梯

问题描述

假设你正在爬楼梯，需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶？

示例：

  • 输入：n = 3
  • 输出：3
  • 解释：有三种方法可以爬到楼顶
    1. 1阶 + 1阶 + 1阶
    2. 1阶 + 2阶
    3. 2阶 + 1阶
解题分析

1. 状态定义

  • dp[i]：到达第 i 阶的方法数

2. 状态转移方程

  • 到达第 i 阶，可以从第 i-1 阶爬1步，或从第 i-2 阶爬2步
  • dp[i] = dp[i-1] + dp[i-2]

3. 初始状态

  • dp[1] = 1（1种方法）
  • dp[2] = 2（2种方法：1+1 或 2）
代码实现
public class ClimbingStairs {
    
    // 方法1：标准动态规划
    public static int climbStairs(int n) {
        // 特殊情况
        if (n <= 2) {
            return n;
        }
        
        // 创建dp数组
        int[] dp = new int[n + 1];
        
        // 初始状态
        dp[1] = 1;
        dp[2] = 2;
        
        // 状态转移
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        
        return dp[n];
    }
    
    // 方法2：空间优化
    public static int climbStairsOptimized(int n) {
        if (n <= 2) {
            return n;
        }
        
        int prev2 = 1;  // dp[i-2]
        int prev1 = 2;  // dp[i-1]
        int current = 0;
        
        for (int i = 3; i <= n; i++) {
            current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }
        
        return current;
    }
    
    // 方法3：如果每次可以爬1、2或3个台阶
    public static int climbStairs3Steps(int n) {
        if (n <= 0) return 0;
        if (n == 1) return 1;
        if (n == 2) return 2;
        if (n == 3) return 4;
        
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        
        for (int i = 4; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }
        
        return dp[n];
    }
    
    // 测试
    public static void main(String[] args) {
        System.out.println("爬5级楼梯的方法数: " + climbStairs(5));  // 8
        System.out.println("爬10级楼梯的方法数: " + climbStairs(10));  // 89
        System.out.println("每次可爬1-3级，爬5级楼梯: " + climbStairs3Steps(5));  // 13
    }
}

时间复杂度：O(n)
空间复杂度：O(n) → 优化后 O(1)

问题3：最小路径和

问题描述

给定一个包含非负整数的 m x n 网格，找出一条从左上角到右下角的路径，使得路径上的数字总和最小。

说明：每次只能向下或向右移动一步。

示例：

输入：grid = [
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出：7
解释：路径 1→3→1→1→1 的总和最小
解题分析

1. 状态定义

  • dp[i][j]：从起点到 (i, j) 的最小路径和

2. 状态转移方程

  • 到达 (i, j) 只能从 (i-1, j) 向下或从 (i, j-1) 向右
  • dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

3. 初始状态

  • 第一行：只能从左边来，dp[0][j] = dp[0][j-1] + grid[0][j]
  • 第一列：只能从上面来，dp[i][0] = dp[i-1][0] + grid[i][0]
代码实现
public class MinPathSum {
    
    // 方法1：标准动态规划
    public static int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        
        int m = grid.length;     // 行数
        int n = grid[0].length;  // 列数
        
        // 创建dp数组
        int[][] dp = new int[m][n];
        
        // 初始状态：起点
        dp[0][0] = grid[0][0];
        
        // 初始化第一行（只能从左边来）
        for (int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }
        
        // 初始化第一列（只能从上边来）
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        
        // 状态转移
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        
        // 返回右下角的值
        return dp[m - 1][n - 1];
    }
    
    // 方法2：空间优化（原地修改）
    public static int minPathSumOptimized(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        
        int m = grid.length;
        int n = grid[0].length;
        
        // 直接在原数组上修改
        // 初始化第一行
        for (int j = 1; j < n; j++) {
            grid[0][j] += grid[0][j - 1];
        }
        
        // 初始化第一列
        for (int i = 1; i < m; i++) {
            grid[i][0] += grid[i - 1][0];
        }
        
        // 状态转移
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
            }
        }
        
        return grid[m - 1][n - 1];
    }
    
    // 方法3：一维数组优化
    public static int minPathSumOptimized2(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        
        int m = grid.length;
        int n = grid[0].length;
        
        // 只需要一维数组
        int[] dp = new int[n];
        dp[0] = grid[0][0];
        
        // 初始化第一行
        for (int j = 1; j < n; j++) {
            dp[j] = dp[j - 1] + grid[0][j];
        }
        
        // 逐行更新
        for (int i = 1; i < m; i++) {
            dp[0] += grid[i][0];  // 第一列
            for (int j = 1; j < n; j++) {
                dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
            }
        }
        
        return dp[n - 1];
    }
    
    // 测试
    public static void main(String[] args) {
        int[][] grid = {
            {1, 3, 1},
            {1, 5, 1},
            {4, 2, 1}
        };
        
        System.out.println("最小路径和: " + minPathSum(grid));  // 7
        
        // 测试空间优化版本
        int[][] grid2 = {
            {1, 3, 1},
            {1, 5, 1},
            {4, 2, 1}
        };
        System.out.println("最小路径和(优化): " + minPathSumOptimized2(grid2));  // 7
    }
}

时间复杂度：O(m × n)
空间复杂度：O(m × n) → 优化后 O(n)

问题4：零钱兑换

问题描述

给定不同面额的硬币 coins 和一个总金额 amount。计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例：

输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
解题分析

1. 状态定义

  • dp[i]：凑成金额 i 所需的最少硬币数

2. 状态转移方程

  • 对于每个金额 i，遍历所有硬币面额 coin
  • 如果 i >= coin，可以使用这个硬币
  • dp[i] = min(dp[i], dp[i - coin] + 1)

3. 初始状态

  • dp[0] = 0（凑成0元需要0个硬币）
  • 其他初始化为无穷大
代码实现
public class CoinChange {
    
    // 标准动态规划
    public static int coinChange(int[] coins, int amount) {
        // 创建dp数组
        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 (i >= coin) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        
        // 如果dp[amount]还是初始值，说明无法凑成
        return dp[amount] > amount ? -1 : dp[amount];
    }
    
    // 带详细注释的版本
    public static int coinChangeWithComments(int[] coins, int amount) {
        // dp[i] 表示凑成金额 i 所需的最少硬币数
        int[] dp = new int[amount + 1];
        
        // 初始化：用一个不可能的大值表示"凑不成"
        Arrays.fill(dp, amount + 1);
        
        // 边界条件：凑成0元需要0个硬币
        dp[0] = 0;
        
        // 遍历所有金额
        for (int i = 1; i <= amount; i++) {
            // 尝试使用每一种硬币
            for (int coin : coins) {
                // 如果当前金额 >= 硬币面额，可以使用这个硬币
                if (i >= coin) {
                    // 状态转移：当前方案 vs 使用这个硬币的方案
                    // dp[i - coin] + 1 表示：先凑出 i-coin，再加一个当前硬币
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
            
            // 调试输出
            System.out.println("凑成金额 " + i + " 需要 " + 
                (dp[i] > amount ? "不可能" : dp[i] + " 个硬币"));
        }
        
        // 检查是否能凑成目标金额
        return dp[amount] > amount ? -1 : dp[amount];
    }
    
    // 记录具体使用的硬币
    public static void coinChangeWithPath(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        int[] choice = new int[amount + 1];  // 记录选择的硬币
        
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (i >= coin && dp[i - coin] + 1 < dp[i]) {
                    dp[i] = dp[i - coin] + 1;
                    choice[i] = coin;  // 记录这一步选择的硬币
                }
            }
        }
        
        if (dp[amount] > amount) {
            System.out.println("无法凑成金额 " + amount);
            return;
        }
        
        // 回溯打印路径
        System.out.println("凑成金额 " + amount + " 需要 " + dp[amount] + " 个硬币：");
        int remaining = amount;
        while (remaining > 0) {
            int coin = choice[remaining];
            System.out.print(coin + " ");
            remaining -= coin;
        }
        System.out.println();
    }
    
    // 测试
    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 11;
        
        System.out.println("最少硬币数: " + coinChange(coins, amount));  // 3
        System.out.println();
        
        coinChangeWithPath(coins, amount);  // 打印具体方案
    }
}

时间复杂度：O(amount × coins.length)
空间复杂度：O(amount)

常见问题类型

类型1：线性DP（一维）

特点：问题可以分解为线性序列的子问题。

经典问题：

  1. 斐波那契数列
  2. 爬楼梯
  3. 打家劫舍
  4. 最长递增子序列
示例：打家劫舍

问题：你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

public class HouseRobber {
    
    public static int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        
        // dp[i] 表示偷到第i家时的最大金额
        int[] dp = new int[nums.length];
        
        // 初始状态
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        
        // 状态转移
        for (int i = 2; i < nums.length; i++) {
            // 偷第i家：dp[i-2] + nums[i]
            // 不偷第i家：dp[i-1]
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        
        return dp[nums.length - 1];
    }
    
    // 空间优化
    public static int robOptimized(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        
        int prev2 = nums[0];
        int prev1 = Math.max(nums[0], nums[1]);
        
        for (int i = 2; i < nums.length; i++) {
            int current = Math.max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = current;
        }
        
        return prev1;
    }
    
    // 测试
    public static void main(String[] args) {
        int[] nums = {2, 7, 9, 3, 1};
        System.out.println("最大金额: " + rob(nums));  // 12 (2+9+1)
    }
}

类型2：二维DP（网格/矩阵）

特点：状态需要用二维数组表示，通常涉及两个维度的决策。

经典问题：

  1. 最小路径和
  2. 不同路径
  3. 编辑距离
  4. 最长公共子序列
示例：编辑距离

问题：给你两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数。你可以对一个单词进行如下三种操作：插入、删除、替换。

public class EditDistance {
    
    public static int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        
        // dp[i][j] 表示 word1 的前 i 个字符转换到 word2 的前 j 个字符需要的最少操作数
        int[][] dp = new int[m + 1][n + 1];
        
        // 初始化：空字符串到另一个字符串的距离
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;  // 删除所有字符
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j;  // 插入所有字符
        }
        
        // 状态转移
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    // 字符相同，不需要操作
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // 字符不同，三种操作取最小
                    dp[i][j] = Math.min(
                        Math.min(
                            dp[i - 1][j] + 1,      // 删除
                            dp[i][j - 1] + 1),     // 插入
                        dp[i - 1][j - 1] + 1       // 替换
                    );
                }
            }
        }
        
        return dp[m][n];
    }
    
    // 带详细输出的版本
    public static int minDistanceWithOutput(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++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j;
        }
        
        // 填充dp表
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(
                        Math.min(dp[i - 1][j], dp[i][j - 1]),
                        dp[i - 1][j - 1]
                    ) + 1;
                }
            }
        }
        
        // 打印dp表
        System.out.println("DP表格：");
        System.out.print("    ");
        for (char c : word2.toCharArray()) {
            System.out.print(c + " ");
        }
        System.out.println();
        
        for (int i = 0; i <= m; i++) {
            if (i > 0) {
                System.out.print(word1.charAt(i - 1) + " ");
            } else {
                System.out.print("  ");
            }
            for (int j = 0; j <= n; j++) {
                System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }
        
        return dp[m][n];
    }
    
    // 测试
    public static void main(String[] args) {
        String word1 = "horse";
        String word2 = "ros";
        
        System.out.println("编辑距离: " + minDistance(word1, word2));  // 3
        System.out.println();
        minDistanceWithOutput(word1, word2);
    }
}

类型3：背包问题

特点：在有限容量下，选择物品使得价值最大化。

经典问题：

  1. 0-1背包
  2. 完全背包
  3. 多重背包
示例：0-1背包

问题：有N个物品和一个容量为W的背包。每个物品有重量w[i]和价值v[i]，每个物品只能使用一次，求解将哪些物品装入背包可使价值总和最大。

public class Knapsack {
    
    // 0-1背包：标准动态规划
    public static int knapsack(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        
        // dp[i][j] 表示前 i 个物品，背包容量为 j 时的最大价值
        int[][] dp = new int[n + 1][capacity + 1];
        
        // 状态转移
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= capacity; j++) {
                if (j < weights[i - 1]) {
                    // 背包容量不够，不能放入第 i 个物品
                    dp[i][j] = dp[i - 1][j];
                } else {
                    // 可以选择放或不放第 i 个物品
                    dp[i][j] = Math.max(
                        dp[i - 1][j],                                    // 不放
                        dp[i - 1][j - weights[i - 1]] + values[i - 1]   // 放
                    );
                }
            }
        }
        
        return dp[n][capacity];
    }
    
    // 一维数组优化
    public static int knapsackOptimized(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        int[] dp = new int[capacity + 1];
        
        // 遍历每个物品
        for (int i = 0; i < n; i++) {
            // 从后向前遍历（避免重复使用同一物品）
            for (int j = capacity; j >= weights[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
            }
        }
        
        return dp[capacity];
    }
    
    // 带路径回溯
    public static void knapsackWithPath(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        int[][] dp = new int[n + 1][capacity + 1];
        
        // 填充dp表
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= capacity; j++) {
                if (j < weights[i - 1]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(
                        dp[i - 1][j],
                        dp[i - 1][j - weights[i - 1]] + values[i - 1]
                    );
                }
            }
        }
        
        // 回溯找出选择的物品
        System.out.println("最大价值: " + dp[n][capacity]);
        System.out.print("选择的物品: ");
        
        int i = n;
        int j = capacity;
        while (i > 0 && j > 0) {
            if (dp[i][j] != dp[i - 1][j]) {
                // 说明选择了第 i 个物品
                System.out.print((i) + " ");
                j -= weights[i - 1];
            }
            i--;
        }
        System.out.println();
    }
    
    // 测试
    public static void main(String[] args) {
        int[] weights = {2, 3, 4, 5};
        int[] values = {3, 4, 5, 6};
        int capacity = 8;
        
        System.out.println("0-1背包最大价值: " + knapsack(weights, values, capacity));  // 10
        System.out.println("0-1背包最大价值(优化): " + knapsackOptimized(weights, values, capacity));  // 10
        System.out.println();
        knapsackWithPath(weights, values, capacity);
    }
}

类型4：区间DP

特点：在一个区间上进行决策，通常需要枚举区间长度和分割点。

经典问题：

  1. 最长回文子串
  2. 矩阵链乘法
  3. 戳气球
示例：最长回文子串
public class LongestPalindrome {
    
    // 动态规划解法
    public static String longestPalindrome(String s) {
        int n = s.length();
        if (n < 2) {
            return s;
        }
        
        // dp[i][j] 表示 s[i...j] 是否是回文串
        boolean[][] dp = new boolean[n][n];
        
        // 所有长度为1的子串都是回文
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }
        
        int start = 0;  // 记录最长回文子串的起始位置
        int maxLen = 1; // 记录最长回文子串的长度
        
        // 枚举子串长度（从2开始）
        for (int len = 2; len <= n; len++) {
            // 枚举左边界
            for (int i = 0; i < n; i++) {
                // 计算右边界
                int j = i + len - 1;
                
                // 越界检查
                if (j >= n) {
                    break;
                }
                
                // 状态转移
                if (s.charAt(i) != s.charAt(j)) {
                    dp[i][j] = false;
                } else {
                    if (len <= 3) {
                        // 长度为2或3，只要首尾相等就是回文
                        dp[i][j] = true;
                    } else {
                        // 长度大于3，还要看去掉首尾后是否是回文
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                
                // 更新最长回文子串
                if (dp[i][j] && len > maxLen) {
                    start = i;
                    maxLen = len;
                }
            }
        }
        
        return s.substring(start, start + maxLen);
    }
    
    // 中心扩展法（更优）
    public static String longestPalindromeCenterExpand(String s) {
        if (s == null || s.length() < 2) {
            return s;
        }
        
        int start = 0;
        int maxLen = 1;
        
        for (int i = 0; i < s.length(); i++) {
            // 奇数长度回文
            int len1 = expandFromCenter(s, i, i);
            // 偶数长度回文
            int len2 = expandFromCenter(s, i, i + 1);
            
            int len = Math.max(len1, len2);
            if (len > maxLen) {
                maxLen = len;
                start = i - (len - 1) / 2;
            }
        }
        
        return s.substring(start, start + maxLen);
    }
    
    private static int expandFromCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }
    
    // 测试
    public static void main(String[] args) {
        String s = "babad";
        System.out.println("最长回文子串: " + longestPalindrome(s));  // "bab" 或 "aba"
        System.out.println("最长回文子串(中心扩展): " + longestPalindromeCenterExpand(s));
    }
}

优化技巧

1. 空间优化

原理：如果当前状态只依赖前面有限的几个状态，可以用变量代替数组。

示例：斐波那契数列

// 空间复杂度从 O(n) 优化到 O(1)
public static int fib(int n) {
    if (n <= 1) return n;
    
    int prev2 = 0;
    int prev1 = 1;
    
    for (int i = 2; i <= n; i++) {
        int current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    
    return prev1;
}

2. 滚动数组

原理：对于二维DP，如果只需要前一行的数据，可以用两个一维数组交替使用。

示例：

// 原来：int[][] dp = new int[m][n];
// 优化：int[][] dp = new int[2][n];

for (int i = 1; i < m; i++) {
    for (int j = 0; j < n; j++) {
        dp[i % 2][j] = dp[(i - 1) % 2][j] + ...;
    }
}

3. 记忆化搜索

原理：在递归的基础上加入缓存，避免重复计算。

示例：

class Solution {
    private Integer[] memo;
    
    public int climbStairs(int n) {
        memo = new Integer[n + 1];
        return helper(n);
    }
    
    private int helper(int n) {
        if (n <= 2) return n;
        if (memo[n] != null) return memo[n];
        
        memo[n] = helper(n - 1) + helper(n - 2);
        return memo[n];
    }
}

实战练习

入门级（建议先完成这些）

  1. 斐波那契数列 (LeetCode 509)
  2. 爬楼梯 (LeetCode 70)
  3. 最大子数组和 (LeetCode 53)
  4. 打家劫舍 (LeetCode 198)
  5. 买卖股票的最佳时机 (LeetCode 121)

进阶级

  1. 最小路径和 (LeetCode 64)
  2. 不同路径 (LeetCode 62)
  3. 零钱兑换 (LeetCode 322)
  4. 最长递增子序列 (LeetCode 300)
  5. 最长公共子序列 (LeetCode 1143)

困难级

  1. 编辑距离 (LeetCode 72)
  2. 正则表达式匹配 (LeetCode 10)
  3. 最长有效括号 (LeetCode 32)
  4. 戳气球 (LeetCode 312)
  5. 俄罗斯套娃信封问题 (LeetCode 354)

学习建议

1. 循序渐进

从最简单的斐波那契和爬楼梯开始，理解动态规划的基本思想。

2. 多做笔记

对于每道题，记录：

  • 状态定义
  • 状态转移方程
  • 初始条件
  • 遍历顺序

3. 画图辅助

用表格或图形展示dp数组的变化过程，帮助理解。

4. 总结模板

总结每种类型问题的通用模板，形成自己的解题框架。

5. 反复练习

动态规划需要大量练习才能熟练掌握，建议每个类型至少做5-10题。

常见错误与调试技巧

错误1：状态定义不清晰

问题：不知道dp[i]到底表示什么。

解决：用简单的例子验证，确保状态定义明确。

错误2：边界条件遗漏

问题：忘记初始化或初始化错误。

解决：先写出最简单情况的答案。

错误3：状态转移方程错误

问题：没有考虑所有可能的转移路径。

解决：画状态转移图，列举所有情况。

错误4：遍历顺序错误

问题：使用了还未计算的状态。

解决：确保使用的状态都已经计算过。

调试技巧

// 打印dp数组
public static void printDpArray(int[] dp) {
    System.out.print("dp数组: [");
    for (int i = 0; i < dp.length; i++) {
        System.out.print(dp[i]);
        if (i < dp.length - 1) System.out.print(", ");
    }
    System.out.println("]");
}

// 打印二维dp数组
public static void printDp2D(int[][] dp) {
    System.out.println("dp数组:");
    for (int[] row : dp) {
        for (int val : row) {
            System.out.printf("%4d", val);
        }
        System.out.println();
    }
}

总结

动态规划是一种强大的算法思想，掌握它需要：

  1. 理解核心思想：把大问题分解为小问题，保存中间结果
  2. 掌握基本步骤：状态定义 → 转移方程 → 初始化 → 遍历 → 返回结果
  3. 大量练习：从简单到复杂，从一维到二维，从线性到区间
  4. 总结归纳：整理不同类型的解题模板

记住：动态规划不是一蹴而就的，需要持续练习和思考。遇到困难是正常的，坚持下去，你一定能掌握这个重要的算法技巧！

祝你学习愉快！🚀

# 动态规划 # 代理模式 # 算法
Logo
乐奇 Rokid 开放社区

更多推荐

cover

Meta Muse 爆火：12 天下载量反超 ChatGPT，个人 AI 智能体完整使用指南

avatar 乐奇 Rokid 开放社区

AI 日报（2026年9月24日）

2026年9月24日，AI技术与应用呈现多元化演进态势。硬件与端侧方面，Meta在Connect大会发布首款轻量化VR眼镜与无摄像头智能眼镜，全面接入Muse智能体；谷歌上线Gemini 3.8 Flash TTS可定制语音模型，并在DeepMind推动私密计算与服务端内存融合。行业与前沿科研领域，Anthropic湿实验实验室利用Claude发现CRISPR样新型酶系统，并推出一站式Claude

avatar 乐奇 Rokid 开放社区
cover

智能眼镜新品扎堆：AR、VR、MR到底怎么分？

avatar 乐奇 Rokid 开放社区