动态规划问题分析与解决指南

---

一、是什么？

动态规划（DP）是一种算法设计技术，用于解决具有重叠子问题和最优子结构特性的复杂问题。核心思想是：

1. 将大问题分解为相互关联的小问题
2. 存储子问题的解（记忆化）避免重复计算
3. 通过子问题的解构建原问题的解

二、解决什么问题

动态规划专门解决以下类型的问题：

1. 最优化问题：求最大值/最小值（如背包最大价值）
2. 计数问题：计算可行方案数量（如路径计数）
3. 存在性问题：判断解是否存在（如子集和问题）
4. 决策问题：需要做出一系列相关决策的问题

三、核心解决步骤

1. 定义状态（最重要的一步）

   • 用 dp[i][j] 或 dp[i] 表示子问题的解
   • 示例：dp[i][j] = 从起点到(i,j)点的最短路径

2. 状态转移方程

   • 描述状态间的递推关系
   • 通用形式：dp[i] = f(dp[i-1], dp[i-2], ...)
   • 示例（斐波那契）：dp[i] = dp[i-1] + dp[i-2]

3. 初始化边界

   • 设置最小子问题的解
   • 示例：dp[0] = 0, dp[1] = 1

4. 确定计算顺序

   • 自底向上（迭代）或自顶向下（递归+记忆化）
   • 保证计算当前状态时，依赖状态已计算

5. 空间优化（进阶）

   • 使用滚动数组减少空间复杂度
   • 示例：斐波那契中只用两个变量代替整个数组

四、应用场景

问题类型	经典问题	状态定义示例
序列问题	最长递增子序列(LIS)	dp[i]=以arr[i]结尾的LIS长度
路径问题	最小路径和	dp[i][j]=到(i,j)的最小和
背包问题	0-1背包	dp[i][w]=前i物品容量w的最大值
字符串匹配	最长公共子序列(LCS)	dp[i][j]=str1[0..i]和str2[0..j]的LCS长度
区间问题	矩阵连乘最小代价	dp[i][j]=矩阵i到j的最小乘法代价

五、Java示例（爬楼梯问题）

问题：每次爬1或2阶，到n阶有多少种方法？

// 动态规划解法
public int climbStairs(int n) {
    if (n <= 2) return n;
    
    // 1. 定义状态：dp[i]表示到达第i阶的方法数
    int[] dp = new int[n + 1];
    
    // 2. 初始化边界
    dp[1] = 1;
    dp[2] = 2;
    
    // 3. 状态转移方程：dp[i] = dp[i-1] + dp[i-2]
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    
    return dp[n];
}

// 空间优化版（滚动数组）
public int climbStairsOptimized(int n) {
    if (n <= 2) return n;
    int prev1 = 1, prev2 = 2;
    for (int i = 3; i <= n; i++) {
        int current = prev1 + prev2;
        prev1 = prev2;
        prev2 = current;
    }
    return prev2;
}

六、与相似技术区别

技术	核心区别	适用场景
分治法	子问题独立无重叠	归并排序、快速排序
贪心算法	局部最优不保证全局最优	最短路径(Dijkstra)
回溯法	暴力搜索+剪枝，复杂度高	排列组合问题
动态规划	存储子问题解，避免重复计算	有重叠子问题场景

七、重要注意事项

1. 必须检查是否满足两个前提条件：

   • 重叠子问题（子问题被重复计算）
   • 最优子结构（全局最优包含局部最优）

2. 避免状态爆炸：

   • 当状态维度太高时（如4维DP），需重新审视问题定义

3. 初始化陷阱：

   • 边界值初始化错误会导致整个结果错误
   • 特别注意0值情况（如空序列、零容量背包）

4. 空间优化时机：

   • 只有当当前状态只依赖有限个前状态时才适用

5. 调试技巧：

   • 打印DP表验证中间结果
   • 使用小规模测试用例验证

八、总结

动态规划问题解决路线图：

1. 识别DP适用特征：寻找"重叠子问题"和"最优子结构"
2. 定义状态：用数学形式描述子问题（80%的工作量在此）
3. 推导转移方程：分析状态间的关系（最难也最关键）
4. 实现算法：选择自底向上（推荐）或自顶向下实现
5. 优化空间：根据依赖关系压缩状态存储

📌 学习建议：从经典问题入手（斐波那契、背包、LCS），先手动画DP表理解状态转移，再尝试独立推导同类问题的状态方程。掌握后，90%的DP问题都可套用此框架解决。