动态规划（DP）算法详解：从入门到精通
一、什么是动态规划？
动态规划（Dynamic Programming，简称 DP）是一种用于求解最优化问题的算法思想。它通过将复杂问题分解为相互重叠的子问题，并存储子问题的解（称为“记忆化”），避免重复计算，从而高效地求解原问题。
动态规划的核心思想可以概括为：最优子结构和重叠子问题。
二、动态规划的核心要素
1. 最优子结构
一个问题的最优解包含其子问题的最优解。这意味着我们可以通过组合子问题的最优解来构造原问题的最优解。
2. 重叠子问题
在递归求解过程中，相同的子问题会被多次计算。动态规划通过存储这些子问题的解（通常使用数组或哈希表）来避免重复计算。
3. 状态转移方程
这是动态规划的核心，描述了问题状态之间的关系。它定义了如何从已知的子问题解推导出当前问题的解。
三、动态规划的解题步骤
- 定义状态：明确 dp 数组（或 dp 表）的含义，dp[i] 或 dp[i][j] 代表什么。
- 确定状态转移方程：找出状态之间的关系式，这是最关键的一步。
- 初始化：确定基础情况，即最简单的子问题的解。
- 确定遍历顺序：确保在计算当前状态时，所需的前置状态已经计算完成。
- 举例推导 dp 数组：通过手动推导小例子验证状态转移方程的正确性。
四、经典动态规划问题示例
1. 斐波那契数列
这是理解动态规划最经典的入门问题。
def fibonacci(n): if n <= 1: return n dp = [0] * (n + 1) dp[0] = 0 dp[1] = 1 for i in range(2, n + 1): dp[i] = dp[i - 1] + dp[i - 2] return dp[n] 时间复杂度：O(n) 空间复杂度：O(n)2. 背包问题（0-1背包）
给定一组物品，每个物品有重量和价值，在不超过背包容量的情况下，如何选择物品使得总价值最大。
public class Knapsack { public int knapsack(int[] weights, int[] values, int capacity) { int n = weights.length; int[][] dp = new int[n + 1][capacity + 1]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= capacity; j++) { if (weights[i - 1] <= j) { dp[i][j] = Math.max( dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1] ); } else { dp[i][j] = dp[i - 1][j]; } } } return dp[n][capacity]; } }3. 最长公共子序列（LCS）
给定两个字符串，找到它们的最长公共子序列的长度。
int longestCommonSubsequence(string text1, string text2) { int m = text1.length(), n = text2.length(); vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (text1[i - 1] == text2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[m][n]; }五、动态规划的优化技巧
1. 空间优化
很多动态规划问题可以将二维 dp 数组优化为一维，减少空间复杂度。
2. 状态压缩
对于状态数有限的问题，可以使用位运算进行状态压缩。
3. 记忆化搜索
采用自顶向下的递归方式，配合缓存（记忆化）来避免重复计算。
六、动态规划的应用场景
- 最优化问题：求最大值、最小值、最优方案
- 计数问题：求方案总数、路径总数
- 可行性问题：判断是否存在满足条件的解
- 序列问题：最长递增子序列、编辑距离等
- 区间问题：矩阵链乘法、石子合并等
七、学习建议与资源
1.从简单问题开始：先掌握斐波那契、爬楼梯等基础问题
2.理解状态定义：不同的状态定义会导致不同的解题思路
3.多画状态转移表：通过表格直观理解状态转移过程
4.刷题平台推荐：LeetCode、牛客网、AcWing
5.经典教材参考：《算法导论》、《算法竞赛入门经典》
八、常见误区与注意事项
- 不要混淆动态规划与分治算法（分治的子问题不重叠）
- 注意边界条件的处理，避免数组越界
- 对于大规模问题，考虑空间优化和剪枝
- 动态规划不是万能的，有些问题可能更适合贪心或回溯