🦋 动态规划详解：从入门到精通

✨ 一文掌握动态规划精髓：状态定义 + 状态转移 + 最优子结构 = 高效解题

🎯 核心思想：将复杂问题分解为重叠子问题，存储子问题的解避免重复计算

📚 适用场景：最优化问题、计数问题、存在性问题等

📖 目录

🎯 什么是动态规划

动态规划（Dynamic Programming，DP）是一种通过将复杂问题分解为更小的重叠子问题来求解的方法。与分治法不同，动态规划会存储子问题的解，避免重复计算。

核心思想

  • 最优子结构：问题的最优解包含子问题的最优解
  • 重叠子问题：问题可以分解为重复出现的子问题
  • 状态存储：用表格存储子问题的解，避免重复计算
  • 无后效性：未来的决策不影响过去的状态

适用场景

  • 最优化问题：求最大值、最小值、最优方案等
  • 计数问题：求方案数、路径数、组合数等
  • 存在性问题：判断是否存在某种方案
  • 字符串问题：编辑距离、最长公共子序列等
  • 背包问题：0-1背包、完全背包、多重背包等

🚀 快速入门指南

🎯 什么是动态规划？

动态规划 = 分治 + 记忆化 + 最优子结构

想象你在爬楼梯：

  • 🏃‍♂️ 第1步：到达第n阶的方法 = 到达第(n-1)阶的方法 + 到达第(n-2)阶的方法
  • 💾 记忆化：记录到达每一阶的方法数，避免重复计算
  • 🎯 最优解：选择到达终点的最优路径

💡 核心四要素

要素 说明 示例
状态定义 描述子问题的变量 dp[i] 表示到达第i阶的方法数
状态转移 状态之间的关系 dp[i] = dp[i-1] + dp[i-2]
初始条件 最小子问题的解 dp[0] = 1, dp[1] = 1
最终结果 原问题的解 dp[n]

🔑 万能模板（记住这个就够了！）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 🎯 步骤1：状态定义
dp[i] 表示...（明确状态的含义）

// 🚀 步骤2：状态转移方程
dp[i] = f(dp[i-1], dp[i-2], ...) // 根据问题特点确定

// 📝 步骤3：初始条件
dp[0] = ... // 最小子问题的解

// 🎨 步骤4：计算顺序
for (int i = 1; i <= n; i++) {
    dp[i] = ... // 按状态转移方程计算
}

// ✅ 步骤5：返回结果
return dp[n]; // 或其他需要的结果

🎨 举个简单例子：爬楼梯问题

假设你正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * 🎯 爬楼梯问题 - 动态规划解法
 * 📝 问题：每次可以爬1或2阶，求到达第n阶的方法数
 * 
 * @param n 楼梯总阶数
 * @return 到达楼顶的方法数
 */
public int climbStairs(int n) {
    // 🛡️ 边界条件处理
    if (n <= 2) return n;
    
    // 📝 步骤1：状态定义
    // dp[i] 表示到达第i阶楼梯的方法数
    int[] dp = new int[n + 1];
    
    // 📝 步骤2：初始条件
    dp[0] = 1;  // 地面有1种方法（不爬）
    dp[1] = 1;  // 第1阶有1种方法
    
    // 🚀 步骤3：状态转移
    for (int i = 2; i <= n; i++) {
        // 到达第i阶的方法 = 从i-1阶爬1阶 + 从i-2阶爬2阶
        dp[i] = dp[i-1] + dp[i-2];
    }
    
    // ✅ 步骤4：返回结果
    return dp[n];
}

/**
 * 🎯 空间优化版本 - 滚动数组
 * 💡 观察到只需要前两个状态，可以将空间复杂度优化到O(1)
 */
public int climbStairsOptimized(int n) {
    if (n <= 2) return n;
    
    int prev2 = 1;  // dp[i-2]
    int prev1 = 1;  // dp[i-1]
    
    for (int i = 2; i <= n; i++) {
        int current = prev1 + prev2;  // dp[i] = dp[i-1] + dp[i-2]
        prev2 = prev1;  // 更新dp[i-2]
        prev1 = current; // 更新dp[i-1]
    }
    
    return prev1;
}

⚡ 一分钟理解动态规划

  1. 定义状态：找到能描述子问题的变量 📊
  2. 找出转移：发现状态之间的关系 🔄
  3. 确定初始：设置最小子问题的解 🎯
  4. 计算结果：按顺序计算所有状态 ✅

关键：状态定义和状态转移方程是核心！

🏗️ 动态规划的基本框架

通用模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class DynamicProgrammingTemplate {
    
    public int solveDP(int[] params) {
        // 1. 参数校验和边界处理
        if (params == null || params.length == 0) {
            return 0;
        }
        
        int n = params.length;
        
        // 2. 状态定义（根据问题复杂度选择一维、二维或多维）
        int[] dp = new int[n + 1];           // 一维DP
        // int[][] dp = new int[n + 1][m + 1]; // 二维DP
        // int[][][] dp = new int[n + 1][m + 1][k + 1]; // 三维DP
        
        // 3. 初始条件设置
        dp[0] = ...; // 最小子问题的解
        
        // 4. 状态转移计算
        for (int i = 1; i <= n; i++) {
            // 根据状态转移方程计算dp[i]
            dp[i] = ...;
            
            // 可能需要考虑多种选择
            for (int j = 0; j < i; j++) {
                dp[i] = Math.max(dp[i], dp[j] + ...);
            }
        }
        
        // 5. 返回最终结果
        return dp[n];
    }
}

框架解析

  1. 状态定义：确定dp数组的维度和含义
  2. 初始条件：设置最小规模子问题的解
  3. 状态转移：建立状态之间的关系方程
  4. 计算顺序：确定状态的计算顺序（通常从小到大）
  5. 结果提取：从dp数组中提取最终答案

🎯 解题四步法：系统攻克DP问题

📝 步骤1：问题分析

🔍 关键问题：

  • ❓ 最优子结构？ 问题能否分解为子问题？
  • ❓ 重叠子问题？ 子问题是否重复出现？
  • ❓ 无后效性？ 未来决策是否影响过去？
  • ❓ 状态如何定义？ 用什么变量描述子问题？

🎨 示例：最长递增子序列

1
2
3
4
问题：求数组中最长的严格递增子序列长度
状态：dp[i] 表示以第i个元素结尾的最长递增子序列长度
转移：dp[i] = max(dp[j] + 1) for all j < i && nums[j] < nums[i]
初始：dp[i] = 1 (每个元素本身就是一个长度为1的递增子序列)

🛠️ 步骤2：状态定义与转移

🎯 状态定义技巧：

  • 一维状态：dp[i] 表示前i个元素的某种性质
  • 二维状态：dp[i][j] 表示前i个元素在状态j下的某种性质
  • 多维状态：根据问题复杂度增加维度

🧩 状态转移方程：

1
2
3
4
5
6
7
8
// 🎯 最值型：求最大值或最小值
dp[i] = max/min(dp[i-1], dp[i-2], ...) + cost

// 🎯 计数型：求方案数
dp[i] = sum(dp[i-1], dp[i-2], ...)

// 🎯 存在型：判断是否存在
dp[i] = dp[i-1] || dp[i-2] || ...

⚡ 步骤3：优化策略

💡 空间优化：

  • 滚动数组：只保留必要的前几个状态
  • 状态压缩：用位运算表示状态
  • 降维打击：减少dp数组的维度

🔪 时间优化：

  • 前缀和/差分：快速计算区间和
  • 单调队列：维护滑动窗口最值
  • 线段树/树状数组：高效区间查询

🧪 步骤4：实现与验证

✅ 实现要点：

  • 边界条件：处理空数组、单元素等特殊情况
  • 循环顺序：确保计算dp[i]时所需的前置状态已计算
  • 状态初始化：正确设置dp数组的初始值

🎯 验证方法：

  • 小规模验证：用简单例子验证状态转移
  • 打印dp数组：调试时输出中间状态
  • 复杂度分析：时间复杂度 = 状态数 × 转移复杂度

🧩 经典问题详解：从理论到实战

🎯 学习目标：通过5个经典问题，掌握动态规划的核心技巧

📊 难度梯度：⭐☆☆☆ → ⭐⭐☆☆ → ⭐⭐⭐☆ → ⭐⭐⭐⭐ → ⭐⭐⭐⭐⭐

💡 核心技巧：状态定义 + 转移方程 + 空间优化

1. 斐波那契数列 ⭐☆☆☆

🎯 LeetCode 509：求第n个斐波那契数

💡 核心思路：经典入门问题，展示DP基本思想

🎨 状态定义：

  • dp[i] 表示第i个斐波那契数
  • 转移方程：dp[i] = dp[i-1] + dp[i-2]
  • 初始条件：dp[0] = 0, dp[1] = 1

基础实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Fibonacci {
    /**
     * 🎯 斐波那契数列 - 动态规划解法
     * 📝 状态：dp[i] 表示第i个斐波那契数
     * 📝 转移：dp[i] = dp[i-1] + dp[i-2]
     */
    public 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * 🎯 空间优化版本 - 滚动数组
 * 💡 只需要前两个状态，空间复杂度O(1)
 */
public int fibOptimized(int n) {
    if (n <= 1) return n;
    
    int prev2 = 0;  // dp[i-2]
    int prev1 = 1;  // dp[i-1]
    
    for (int i = 2; i <= n; i++) {
        int current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    
    return prev1;
}

2. 零钱兑换 ⭐⭐☆☆

🎯 LeetCode 322：给定不同面额的硬币和一个总金额，求最少需要多少枚硬币

💡 核心思路：完全背包问题的变种，求最少物品数

🎨 状态定义：

  • dp[i] 表示凑齐金额i所需的最少硬币数
  • 转移方程：dp[i] = min(dp[i], dp[i-coin] + 1) for each coin
  • 初始条件：dp[0] = 0，其他为无穷大

完整实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public class CoinChange {
    /**
     * 🎯 零钱兑换 - 最少硬币数
     * 📝 状态：dp[i] 表示凑齐金额i的最少硬币数
     * 📝 转移：dp[i] = min(dp[i], dp[i-coin] + 1)
     */
    public int coinChange(int[] coins, int amount) {
        // 📝 步骤1：状态定义
        // dp[i] 表示凑齐金额i所需的最少硬币数
        int[] dp = new int[amount + 1];
        
        // 📝 步骤2：初始条件
        // dp[0] = 0，其他设置为无穷大（表示不可达）
        Arrays.fill(dp, amount + 1);  // 用amount+1表示无穷大
        dp[0] = 0;
        
        // 🚀 步骤3：状态转移
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i) {  // 硬币面额不超过当前金额
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        
        // ✅ 步骤4：返回结果
        return dp[amount] > amount ? -1 : dp[amount];
    }
    
    /**
     * 🎯 零钱兑换 - 求所有方案数
     * 💡 将min换成sum，求方案总数
     */
    public int coinChangeWays(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;  // 凑齐0元有1种方法（不选任何硬币）
        
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i) {
                    dp[i] += dp[i - coin];
                }
            }
        }
        
        return dp[amount];
    }
}

3. 最长递增子序列 ⭐⭐⭐☆

🎯 LeetCode 300：求数组中最长的严格递增子序列长度

💡 核心思路：序列DP，需要比较前面所有状态

🎨 状态定义：

  • dp[i] 表示以第i个元素结尾的最长递增子序列长度
  • 转移方程：dp[i] = max(dp[j] + 1) for all j < i && nums[j] < nums[i]
  • 初始条件：dp[i] = 1 (每个元素本身就是一个长度为1的序列)

完整实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
public class LongestIncreasingSubsequence {
    /**
     * 🎯 最长递增子序列 - 动态规划解法
     * 📝 状态：dp[i] 表示以第i个元素结尾的最长递增子序列长度
     * 📝 转移：dp[i] = max(dp[j] + 1) for all j < i && nums[j] < nums[i]
     */
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        
        int n = nums.length;
        
        // 📝 状态定义
        int[] dp = new int[n];
        
        // 📝 初始条件：每个元素本身就是一个长度为1的序列
        Arrays.fill(dp, 1);
        
        int maxLength = 1;
        
        // 🚀 状态转移
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {  // 满足递增条件
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLength = Math.max(maxLength, dp[i]);
        }
        
        return maxLength;
    }
    
    /**
     * 🎯 贪心 + 二分查找优化 - O(nlogn)
     * 💡 维护一个递增序列，用二分查找优化
     */
    public int lengthOfLISOptimized(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        
        List<Integer> tails = new ArrayList<>();
        
        for (int num : nums) {
            int left = 0, right = tails.size();
            
            // 二分查找插入位置
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (tails.get(mid) < num) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            
            if (left == tails.size()) {
                tails.add(num);  // 比所有元素都大，扩展序列
            } else {
                tails.set(left, num);  // 替换，维护最小尾部元素
            }
        }
        
        return tails.size();
    }
}

4. 编辑距离 ⭐⭐⭐⭐

🎯 LeetCode 72：求两个字符串之间的最小编辑距离（插入、删除、替换）

💡 核心思路：二维DP，两个字符串的匹配问题

🎨 状态定义：

  • dp[i][j] 表示word1的前i个字符和word2的前j个字符之间的最小编辑距离
  • 转移方程：
    • 如果字符相等：dp[i][j] = dp[i-1][j-1]
    • 如果字符不等：dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
  • 初始条件：dp[i][0] = i，dp[0][j] = j

完整实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public class EditDistance {
    /**
     * 🎯 编辑距离 - 动态规划解法
     * 📝 状态：dp[i][j] 表示word1前i字符和word2前j字符的最小编辑距离
     * 📝 操作：插入、删除、替换
     */
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        
        // 📝 状态定义
        int[][] dp = new int[m + 1][n + 1];
        
        // 📝 初始条件
        // word1前i字符变成空字符串需要i次删除
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        // 空字符串变成word2前j字符需要j次插入
        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 {
                    // 字符不等，取三种操作的最小值
                    int replace = dp[i-1][j-1] + 1;  // 替换
                    int delete = dp[i-1][j] + 1;   // 删除
                    int insert = dp[i][j-1] + 1;   // 插入
                    dp[i][j] = Math.min(Math.min(replace, delete), insert);
                }
            }
        }
        
        return dp[m][n];
    }
}

5. 正则表达式匹配 ⭐⭐⭐⭐⭐

🎯 LeetCode 10：实现正则表达式匹配，支持.和*

💡 核心思路：二维DP，处理通配符匹配的复杂情况

🎨 状态定义：

  • dp[i][j] 表示s的前i个字符和p的前j个字符是否匹配
  • 转移方程：
    • 如果p[j-1]不是*：直接比较字符
    • 如果p[j-1]是*：考虑匹配0个或多个前驱字符
  • 初始条件：dp[0][0] = true，处理空字符串匹配

完整实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public class RegularExpressionMatching {
    /**
     * 🎯 正则表达式匹配 - 动态规划解法
     * 📝 状态：dp[i][j] 表示s前i字符和p前j字符是否匹配
     * 📝 通配符：. 匹配任意字符，* 匹配前面字符0次或多次
     */
    public boolean isMatch(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];  // *匹配0个前驱字符
            }
        }
        
        // 🚀 状态转移
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p.charAt(j-1) == '*') {
                    // 处理*通配符
                    char prevChar = p.charAt(j-2);
                    // *匹配0个前驱字符
                    dp[i][j] = dp[i][j-2];
                    // *匹配1个或多个前驱字符
                    if (prevChar == '.' || prevChar == s.charAt(i-1)) {
                        dp[i][j] = dp[i][j] || dp[i-1][j];
                    }
                } else if (p.charAt(j-1) == '.') {
                    // 处理.通配符
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    // 普通字符匹配
                    dp[i][j] = dp[i-1][j-1] && (s.charAt(i-1) == p.charAt(j-1));
                }
            }
        }
        
        return dp[m][n];
    }
}

6. 0/1背包问题 ⭐⭐⭐⭐⭐

🎯 经典问题：有N件物品和一个容量为W的背包，第i件物品的重量是w[i]，价值是v[i]，求解将哪些物品装入背包可使这些物品的总重量不超过背包容量，且价值总和最大。

💡 核心思路：二维DP，每个物品只能选择一次（0/1选择）

🎨 状态定义：

  • dp[i][j] 表示前i件物品放入容量为j的背包中的最大价值
  • 转移方程：
    • 不选第i件物品：dp[i][j] = dp[i-1][j]
    • 选第i件物品：dp[i][j] = dp[i-1][j-w[i-1]] + v[i-1]（前提是j ≥ w[i-1]）
  • 初始条件：dp[0][j] = 0（0件物品价值为0）

完整实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
public class KnapsackProblem {
    /**
     * 🎯 0/1背包问题 - 动态规划解法
     * 📝 状态：dp[i][j] 表示前i件物品放入容量为j的背包中的最大价值
     * 📝 选择：对于每件物品，可以选择放入或不放入背包
     */
    public int knapsack(int W, int[] weights, int[] values) {
        int n = weights.length;
        
        // 📝 状态定义
        int[][] dp = new int[n + 1][W + 1];
        
        // 📝 初始条件：dp[0][j] = 0（0件物品价值为0）
        
        // 🚀 状态转移
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= W; j++) {
                // 不选第i件物品
                dp[i][j] = dp[i-1][j];
                
                // 选第i件物品（前提是容量足够）
                if (j >= weights[i-1]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-weights[i-1]] + values[i-1]);
                }
            }
        }
        
        return dp[n][W];
    }
    
    /**
     * 🎯 0/1背包问题 - 空间优化版本（滚动数组）
     * 💡 将二维DP优化为一维DP，空间复杂度从O(nW)降到O(W)
     */
    public int knapsackOptimized(int W, int[] weights, int[] values) {
        int n = weights.length;
        
        // 📝 一维状态定义
        int[] dp = new int[W + 1];
        
        // 🚀 状态转移（逆序遍历容量，避免重复选择）
        for (int i = 0; i < n; i++) {
            for (int j = W; j >= weights[i]; j--) {
                // 选或不选当前物品，取最大值
                dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
            }
        }
        
        return dp[W];
    }
    
    /**
     * 🎯 背包问题变种 - 恰好装满背包
     * 💡 求恰好装满容量W的最大价值，若无法装满返回-1
     */
    public int knapsackExact(int W, int[] weights, int[] values) {
        int n = weights.length;
        int[] dp = new int[W + 1];
        
        // 📝 初始条件：除了dp[0]，其他都设为负无穷（表示不可达）
        Arrays.fill(dp, Integer.MIN_VALUE);
        dp[0] = 0;
        
        // 🚀 状态转移
        for (int i = 0; i < n; i++) {
            for (int j = W; j >= weights[i]; j--) {
                if (dp[j - weights[i]] != Integer.MIN_VALUE) {
                    dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
                }
            }
        }
        
        // 📝 如果dp[W]仍然是负无穷，说明无法恰好装满
        return dp[W] == Integer.MIN_VALUE ? -1 : dp[W];
    }
}

⚡ 优化技巧与高级策略

🎯 空间优化技巧

1. 滚动数组优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * 🎯 滚动数组优化 - 适用于只依赖前几个状态的情况
 * 💡 将O(n)空间优化为O(1)或O(k)
 */
public int rollingArrayOptimization(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;
}

2. 状态压缩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * 🎯 状态压缩 - 用位运算表示状态
 * 💡 适用于状态是布尔值的情况
 */
public boolean stateCompression(String s, String p) {
    int m = s.length();
    int n = p.length();
    
    // 用位掩码表示状态
    long[] dp = new long[m + 1];
    dp[0] = 1L;  // 初始状态
    
    for (int j = 1; j <= n; j++) {
        long[] newDp = new long[m + 1];
        
        for (int i = 0; i <= m; i++) {
            // 用位运算处理状态转移
            if (i > 0 && (s.charAt(i-1) == p.charAt(j-1) || p.charAt(j-1) == '.')) {
                newDp[i] |= dp[i-1];
            }
            // 其他状态转移...
        }
        
        dp = newDp;
    }
    
    return dp[m] != 0;
}

🎯 时间优化策略

1. 单调队列优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * 🎯 单调队列优化 - 适用于滑动窗口最值问题
 * 💡 将O(n²)优化为O(n)
 */
public int maxSumWithMonotonicQueue(int[] nums, int k) {
    int n = nums.length;
    int[] dp = new int[n + 1];
    
    // 单调队列，维护窗口中的最大值索引
    Deque<Integer> deque = new LinkedList<>();
    
    for (int i = 1; i <= n; i++) {
        // 维护队列单调性
        while (!deque.isEmpty() && dp[deque.peekLast()] <= dp[i-1]) {
            deque.pollLast();
        }
        
        deque.offerLast(i-1);
        
        // 移除超出窗口范围的元素
        while (deque.peekFirst() < i - k) {
            deque.pollFirst();
        }
        
        // 当前最大值
        dp[i] = dp[deque.peekFirst()] + nums[i-1];
    }
    
    return dp[n];
}

2. 斜率优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * 🎯 斜率优化 - 适用于特定形式的DP方程
 * 💡 将O(n²)优化为O(n)
 */
public int slopeOptimization(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    
    // 凸包优化，维护决策点的凸包
    List<Integer> convexHull = new ArrayList<>();
    
    for (int i = 0; i < n; i++) {
        // 在凸包上二分查找最优决策点
        int left = 0, right = convexHull.size() - 1;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (compareSlopes(convexHull.get(mid), convexHull.get(mid + 1), i) <= 0) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        int bestJ = convexHull.get(left);
        dp[i] = calculateValue(bestJ, i);
        
        // 维护凸包
        while (convexHull.size() >= 2 && 
               compareSlopes(convexHull.get(convexHull.size()-2), 
                           convexHull.get(convexHull.size()-1), i) >= 0) {
            convexHull.remove(convexHull.size() - 1);
        }
        
        convexHull.add(i);
    }
    
    return dp[n-1];
}

private int compareSlopes(int j1, int j2, int i) {
    // 斜率比较逻辑...
    return 0;
}

private int calculateValue(int j, int i) {
    // 值计算逻辑...
    return 0;
}

🏢 实际应用案例

案例1：股票买卖问题

场景描述：给定股票价格数组，求最大利润，有交易次数限制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
public class StockTrading {
    /**
     * 🎯 股票买卖III - 最多两次交易
     * 📝 状态：buy1, sell1, buy2, sell2 表示第一次和第二次交易的状态
     */
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2) return 0;
        
        // 📝 状态定义
        // firstBuy: 第一次买入后的最大利润（负数）
        // firstSell: 第一次卖出后的最大利润
        // secondBuy: 第二次买入后的最大利润
        // secondSell: 第二次卖出后的最大利润
        int firstBuy = -prices[0];
        int firstSell = 0;
        int secondBuy = -prices[0];
        int secondSell = 0;
        
        // 🚀 状态转移
        for (int i = 1; i < prices.length; i++) {
            firstBuy = Math.max(firstBuy, -prices[i]);  // 第一次买入
            firstSell = Math.max(firstSell, firstBuy + prices[i]);  // 第一次卖出
            secondBuy = Math.max(secondBuy, firstSell - prices[i]);  // 第二次买入
            secondSell = Math.max(secondSell, secondBuy + prices[i]);  // 第二次卖出
        }
        
        return secondSell;
    }
    
    /**
     * 🎯 股票买卖IV - 最多k次交易
     * 💡 通用解法，适用于任意交易次数限制
     */
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        if (n < 2) return 0;
        
        // 如果k很大，相当于没有限制
        if (k >= n / 2) {
            return maxProfitUnlimited(prices);
        }
        
        // 📝 状态定义
        // dp[i][j] 表示最多i次交易，第j天的最大利润
        int[][] dp = new int[k + 1][n];
        
        // 🚀 状态转移
        for (int i = 1; i <= k; i++) {
            int maxDiff = -prices[0];  // 记录之前的最大利润差
            
            for (int j = 1; j < n; j++) {
                // 要么今天不交易，要么今天卖出
                dp[i][j] = Math.max(dp[i][j-1], prices[j] + maxDiff);
                // 更新最大利润差，用于明天的交易
                maxDiff = Math.max(maxDiff, dp[i-1][j] - prices[j]);
            }
        }
        
        return dp[k][n-1];
    }
    
    private int maxProfitUnlimited(int[] prices) {
        int profit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i-1]) {
                profit += prices[i] - prices[i-1];
            }
        }
        return profit;
    }
}

案例2：任务调度问题

场景描述：有n个任务，每个任务有截止时间和利润，安排任务执行顺序使总利润最大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
public class TaskSchedulingDP {
    static class Task {
        int deadline;
        int profit;
        
        Task(int deadline, int profit) {
            this.deadline = deadline;
            this.profit = profit;
        }
    }
    
    /**
     * 🎯 任务调度 - 最大利润
     * 📝 状态：dp[i] 表示在时间i内能获得的最大利润
     * 💡 按截止时间排序，使用动态规划
     */
    public int scheduleTasks(Task[] tasks) {
        // 按截止时间排序
        Arrays.sort(tasks, (a, b) -> a.deadline - b.deadline);
        
        int maxDeadline = tasks[tasks.length - 1].deadline;
        
        // 📝 状态定义
        int[] dp = new int[maxDeadline + 1];
        
        int taskIndex = 0;
        
        // 🚀 状态转移
        for (int time = 1; time <= maxDeadline; time++) {
            dp[time] = dp[time - 1];  // 不执行任何任务
            
            // 考虑在时间time执行的任务
            while (taskIndex < tasks.length && tasks[taskIndex].deadline == time) {
                Task task = tasks[taskIndex];
                
                // 要么不执行这个任务，要么执行这个任务
                for (int start = 0; start < time; start++) {
                    if (dp[start] + task.profit > dp[time]) {
                        dp[time] = dp[start] + task.profit;
                    }
                }
                
                taskIndex++;
            }
        }
        
        return dp[maxDeadline];
    }
    
    /**
     * 🎯 任务调度 - 带权重的完成时间最小化
     * 📝 状态：dp[i][j] 表示前i个任务，总完成时间为j的最小加权完成时间
     */
    public int minimizeWeightedCompletionTime(int[] durations, int[] weights) {
        int n = durations.length;
        int totalTime = Arrays.stream(durations).sum();
        
        // 📝 状态定义
        int[][] dp = new int[n + 1][totalTime + 1];
        
        // 🚀 状态转移
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= totalTime; j++) {
                dp[i][j] = dp[i-1][j];  // 不选择第i个任务
                
                if (j >= durations[i-1]) {
                    int completionTime = j;
                    int weightedTime = weights[i-1] * completionTime;
                    dp[i][j] = Math.min(dp[i][j], dp[i-1][j - durations[i-1]] + weightedTime);
                }
            }
        }
        
        return dp[n][totalTime];
    }
}

⚡ 性能分析

时间复杂度

动态规划的时间复杂度取决于状态数和状态转移复杂度：

问题类型 状态数 转移复杂度 总复杂度 示例
一维线性DP O(n) O(1) O(n) 斐波那契数列
一维线性DP O(n) O(n) O(n²) 最长递增子序列
二维DP O(n²) O(1) O(n²) 编辑距离
二维DP O(n²) O(n) O(n³) 最优三角形剖分
三维DP O(n³) O(1) O(n³) 矩阵链乘法
状态压缩DP O(2ⁿ) O(1) O(2ⁿ) 旅行商问题

空间复杂度

  • 基础DP：O(n) 或 O(n²)，存储所有状态
  • 滚动数组优化：O(1) 或 O(n)，只保留必要状态
  • 状态压缩：O(2ⁿ) 或 O(n×2ⁿ)，用位运算表示状态

优化效果对比

优化方法 时间复杂度 空间复杂度 适用场景 优化效果
基础DP O(n²) O(n²) 通用 基准线
滚动数组 O(n²) O(n) 状态只依赖前几行 空间优化
单调队列 O(n) O(n) 滑动窗口最值 时间优化
斜率优化 O(n) O(n) 特定形式DP方程 时间优化
状态压缩 O(2ⁿ) O(2ⁿ) 状态是布尔值 空间优化

🎯 实战练习：LeetCode经典DP题目

🎯 练习目标：通过刷题巩固动态规划核心技巧

📊 难度分布：简单(30%) | 中等(50%) | 困难(20%)

💡 练习建议：按类型刷题，总结规律，形成直觉

🌟 基础题目（必做）

1. 线性DP（一维）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/**
 * 🎯 LeetCode 70. 爬楼梯
 * 💡 最基础的DP入门题
 */
public int climbStairs(int n) {
    if (n <= 2) return n;
    
    int prev2 = 1, prev1 = 2;
    for (int i = 3; i <= n; i++) {
        int current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    
    return prev1;
}

/**
 * 🎯 LeetCode 198. 打家劫舍
 * 💡 不能连续选择相邻元素的DP问题
 */
public int rob(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    if (nums.length == 1) return nums[0];
    
    int prev2 = 0;  // dp[i-2]
    int prev1 = 0;  // dp[i-1]
    
    for (int num : nums) {
        int current = Math.max(prev1, prev2 + num);
        prev2 = prev1;
        prev1 = current;
    }
    
    return prev1;
}

/**
 * 🎯 LeetCode 413. 等差数列划分
 * 💡 需要找规律的DP问题
 */
public int numberOfArithmeticSlices(int[] nums) {
    int n = nums.length;
    if (n < 3) return 0;
    
    int[] dp = new int[n];
    int total = 0;
    
    for (int i = 2; i < n; i++) {
        if (nums[i] - nums[i-1] == nums[i-1] - nums[i-2]) {
            dp[i] = dp[i-1] + 1;
            total += dp[i];
        }
    }
    
    return total;
}

2. 背包问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/**
 * 🎯 LeetCode 416. 分割等和子集
 * 💡 0-1背包问题的变种
 */
public boolean canPartition(int[] nums) {
    int sum = Arrays.stream(nums).sum();
    if (sum % 2 != 0) return false;
    
    int target = sum / 2;
    boolean[] dp = new boolean[target + 1];
    dp[0] = true;
    
    for (int num : nums) {
        for (int j = target; j >= num; j--) {
            dp[j] = dp[j] || dp[j - num];
        }
    }
    
    return dp[target];
}

/**
 * 🎯 LeetCode 494. 目标和
 * 💡 背包问题求方案数
 */
public int findTargetSumWays(int[] nums, int target) {
    int sum = Arrays.stream(nums).sum();
    if (Math.abs(target) > sum) return 0;
    
    int newTarget = (sum + target) / 2;
    if ((sum + target) % 2 != 0) return 0;
    
    int[] dp = new int[newTarget + 1];
    dp[0] = 1;
    
    for (int num : nums) {
        for (int j = newTarget; j >= num; j--) {
            dp[j] += dp[j - num];
        }
    }
    
    return dp[newTarget];
}

/**
 * 🎯 LeetCode 474. 一和零
 * 💡 多维背包问题
 */
public int findMaxForm(String[] strs, int m, int n) {
    int[][] dp = new int[m + 1][n + 1];
    
    for (String str : strs) {
        int[] count = countZerosAndOnes(str);
        int zeros = count[0];
        int ones = count[1];
        
        for (int i = m; i >= zeros; i--) {
            for (int j = n; j >= ones; j--) {
                dp[i][j] = Math.max(dp[i][j], dp[i - zeros][j - ones] + 1);
            }
        }
    }
    
    return dp[m][n];
}

private int[] countZerosAndOnes(String str) {
    int[] count = new int[2];
    for (char c : str.toCharArray()) {
        count[c - '0']++;
    }
    return count;
}

🚀 进阶题目（选做）

1. 区间DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
 * 🎯 LeetCode 516. 最长回文子序列
 * 💡 区间DP的经典题目
 */
public int longestPalindromeSubseq(String s) {
    int n = s.length();
    int[][] dp = new int[n][n];
    
    // 单个字符是长度为1的回文
    for (int i = 0; i < n; i++) {
        dp[i][i] = 1;
    }
    
    // 区间长度从2到n
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            
            if (s.charAt(i) == s.charAt(j)) {
                dp[i][j] = dp[i+1][j-1] + 2;
            } else {
                dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
            }
        }
    }
    
    return dp[0][n-1];
}

/**
 * 🎯 LeetCode 647. 回文子串
 * 💡 计数型的区间DP
 */
public int countSubstrings(String s) {
    int n = s.length();
    boolean[][] dp = new boolean[n][n];
    int count = 0;
    
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            if (s.charAt(i) == s.charAt(j)) {
                if (j - i <= 1) {
                    dp[i][j] = true;
                } else {
                    dp[i][j] = dp[i+1][j-1];
                }
                
                if (dp[i][j]) {
                    count++;
                }
            }
        }
    }
    
    return count;
}

2. 状态压缩DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * 🎯 LeetCode 691. 贴纸拼词
 * 💡 状态压缩DP，用位掩码表示字符使用情况
 */
public int minStickers(String[] stickers, String target) {
    int m = target.length();
    int finalState = (1 << m) - 1;  // 所有字符都被使用的状态
    
    // 预处理每个贴纸能提供哪些字符
    int[][] stickerCounts = new int[stickers.length][26];
    for (int i = 0; i < stickers.length; i++) {
        for (char c : stickers[i].toCharArray()) {
            stickerCounts[i][c - 'a']++;
        }
    }
    
    // dp[state] 表示达到state状态需要的最少贴纸数
    int[] dp = new int[finalState + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;  // 初始状态不需要贴纸
    
    for (int state = 0; state < finalState; state++) {
        if (dp[state] == Integer.MAX_VALUE) continue;
        
        // 尝试使用每个贴纸
        for (int i = 0; i < stickers.length; i++) {
            int newState = state;
            int[] tempCounts = stickerCounts[i].clone();
            
            // 使用贴纸i能覆盖target中的哪些字符
            for (int j = 0; j < m; j++) {
                if (((state >> j) & 1) == 0 && tempCounts[target.charAt(j) - 'a'] > 0) {
                    newState |= (1 << j);
                    tempCounts[target.charAt(j) - 'a']--;
                }
            }
            
            if (newState != state) {
                dp[newState] = Math.min(dp[newState], dp[state] + 1);
            }
        }
    }
    
    return dp[finalState] == Integer.MAX_VALUE ? -1 : dp[finalState];
}

📊 相关LeetCode题目

🎯 基础题目（⭐ 简单）

  1. 509. 斐波那契数 - 最基础的DP入门
  2. 70. 爬楼梯 - 线性DP的经典入门
  3. 746. 使用最小花费爬楼梯 - 带权重的爬楼梯
  4. 198. 打家劫舍 - 不能相邻选择的DP
  5. 413. 等差数列划分 - 需要发现规律的DP

🚀 进阶题目（⭐⭐ 中等）

  1. 322. 零钱兑换 - 完全背包问题的经典应用
  2. 300. 最长递增子序列 - 序列DP的经典题目
  3. 1143. 最长公共子序列 - 两个序列的DP匹配
  4. 416. 分割等和子集 - 0-1背包问题的变种
  5. 494. 目标和 - 背包问题求方案数

🔥 高级题目（⭐⭐⭐ 困难）

  1. 72. 编辑距离 - 二维DP的经典应用
  2. 10. 正则表达式匹配 - 带通配符的复杂DP
  3. 115. 不同的子序列 - 复杂的字符串DP匹配
  4. 123. 买卖股票的最佳时机III - 多状态DP管理
  5. 188. 买卖股票的最佳时机IV - 通用股票交易DP

🧠 记忆口诀

🎯 动态规划四要素

  1. 状态定义：找到能描述子问题的变量 📊
  2. 状态转移：发现状态之间的关系 🔄
  3. 初始条件：设置最小子问题的解 🎯
  4. 最终结果：从dp数组中提取答案 ✅

🔍 DP问题识别口诀

1
2
3
4
📝 最优子结构？能分解为子问题！
🔄 重叠子问题？子问题重复出现！
⚡ 无后效性？未来不影响过去！
💾 存储子解？避免重复计算！

🎨 状态定义技巧

1
2
3
4
📏 一维线性：dp[i] 表示前i个元素
🔄 二维表格：dp[i][j] 表示两个序列匹配
⏰ 时间维度：dp[i][t] 表示前i个元素时间t的状态
💰 多重约束：dp[i][j][k] 表示多个维度的状态

⚡ 优化口诀

1
2
3
4
🚀 滚动数组：空间换时间，只保留必要状态！
🔪 单调队列：滑动窗口最值，O(n²)变O(n)！
📐 斜率优化：特定方程形式，大幅提升效率！
🔧 状态压缩：位运算表示状态，节省空间！

📖 参考资料

🎓 学习总结：动态规划知识图谱

🗺️ 知识架构图

1
2
3
4
5
6
7
8
动态规划 🦋
├── 核心思想 (最优子结构 + 重叠子问题)
├── 基本框架 (状态定义 + 转移方程 + 初始条件)
├── 解题四步法 (分析 → 定义 → 转移 → 优化)
├── 经典问题 (斐波那契 + 背包 + LIS + 编辑距离)
├── 优化技巧 (滚动数组 + 单调队列 + 斜率优化)
├── 高级应用 (区间DP + 状态压缩 + 树形DP)
└── 实战练习 (LeetCode 经典DP题库)

🎯 掌握程度自测

掌握程度 标准 检验方式
入门 ⭐ 理解基本概念，能看懂代码 手写斐波那契数列
熟练 ⭐⭐ 能独立解决基础DP问题 解决爬楼梯和零钱兑换
精通 ⭐⭐⭐ 掌握优化技巧，能举一反三 解决LIS和编辑距离优化
专家 ⭐⭐⭐⭐ 能解决复杂DP问题 解决股票交易和正则匹配

🚀 进阶学习路线

  1. 🎯 基础巩固：熟练掌握三大DP类型（线性、背包、序列）
  2. ⚡ 技巧提升：深入学习空间优化和时间优化策略
  3. 🏗️ 高级应用：掌握区间DP、状态压缩DP、树形DP
  4. 🔬 算法研究：探索四边形不等式、凸优化等高级技巧

💡 学习建议

1
2
3
4
5
📝 建议1：从简单问题入手，理解DP核心思想
📝 建议2：多画图辅助理解，可视化状态转移过程
📝 建议3：重视状态定义，这是DP解题的关键
📝 建议4：掌握优化技巧，提升算法效率
📝 建议5：按类型刷题，总结规律和模板

最后更新：2025-01-15