一、什么是动态规划动态规划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(); vectorvectorint dp(m 1, vectorint(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、牛客网、AcWing5.经典教材参考《算法导论》、《算法竞赛入门经典》八、常见误区与注意事项不要混淆动态规划与分治算法分治的子问题不重叠注意边界条件的处理避免数组越界对于大规模问题考虑空间优化和剪枝动态规划不是万能的有些问题可能更适合贪心或回溯