动态规划算法详解（附代码实现）

一、动态规划的本质与核心思想

动态规划（Dynamic Programming, DP）是一种通过将复杂问题分解为相互依赖的子问题，并存储子问题解以避免重复计算的算法设计范式。其核心在于状态定义与状态转移方程的构建，通过填表（自底向上）或递归加记忆化（自顶向下）的方式高效求解。

1.1 动态规划的适用条件

• 最优子结构：问题的最优解包含子问题的最优解。
• 重叠子问题：子问题在递归过程中被重复计算。
• 无后效性：当前状态仅由之前状态决定，与后续状态无关。

1.2 与分治法的区别

分治法（如归并排序）将问题分解为独立子问题，而动态规划的子问题存在依赖关系，需通过状态转移建立联系。

二、动态规划的分类与实现方式

2.1 按问题类型分类

1. 线性DP：状态呈一维线性结构（如斐波那契数列）。
2. 区间DP：状态与区间相关（如矩阵链乘法）。
3. 背包DP：资源分配问题（如0-1背包）。
4. 状态压缩DP：用二进制位表示状态（如旅行商问题）。

2.2 按实现方式分类

1. 递归+记忆化（自顶向下）

   # 斐波那契数列（记忆化递归）
   memo = {}
   def fib_memo(n):
       if n in memo: return memo[n]
       if n <= 1: return n
       memo[n] = fib_memo(n-1) + fib_memo(n-2)
       return memo[n]

2. 迭代填表（自底向上）

   # 斐波那契数列（迭代）
   def fib_dp(n):
       dp = [0]*(n+1)
       dp[0], dp[1] = 0, 1
       for i in range(2, n+1):
           dp[i] = dp[i-1] + dp[i-2]
       return dp[n]

三、经典动态规划问题详解

3.1 0-1背包问题

问题描述：给定容量为W的背包和N个物品，每个物品有重量w和价值v，求最大价值。

状态定义：dp[i][j]表示前i个物品在容量j下的最大价值。

状态转移方程：

• 不选第i个物品：dp[i][j] = dp[i-1][j]
• 选第i个物品：dp[i][j] = dp[i-1][j-w] + v（若j≥w）
• 综合：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)

代码实现（Python）：

def knapsack(W, wt, val, n):
    dp = [[0]*(W+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, W+1):
            if wt[i-1] > j:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], val[i-1] + dp[i-1][j-wt[i-1]])
    return dp[n][W]

3.2 最长公共子序列（LCS）

问题描述：求两个字符串的最长公共子序列长度。

状态定义：dp[i][j]表示字符串A前i个字符与字符串B前j个字符的LCS长度。

状态转移方程：

• 若A[i-1] == B[j-1]：dp[i][j] = dp[i-1][j-1] + 1
• 否则：dp[i][j] = max(dp[i-1][j], dp[i][j-1])

代码实现（Java）：

public int lcs(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    int[][] dp = new int[m+1][n+1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1.charAt(i-1) == s2.charAt(j-1)) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    return dp[m][n];
}

3.3 数字三角形问题

问题描述：给定一个数字三角形，从顶部到底部找到一条路径，使路径上数字之和最大。

状态定义：dp[i][j]表示从第i行第j列到底部的最大路径和。

状态转移方程：
dp[i][j] = triangle[i][j] + max(dp[i+1][j], dp[i+1][j+1])

代码实现（Python）：

def max_path(triangle):
    n = len(triangle)
    dp = [[0]*n for _ in range(n)]
    # 从底部向上计算
    for i in range(n-1, -1, -1):
        for j in range(i+1):
            if i == n-1:
                dp[i][j] = triangle[i][j]
            else:
                dp[i][j] = triangle[i][j] + max(dp[i+1][j], dp[i+1][j+1])
    return dp[0][0]

四、动态规划的优化技巧

4.1 空间优化

• 滚动数组：将二维DP数组优化为一维。例如背包问题中，dp[j] = max(dp[j], dp[j-w] + v)。
• 状态压缩：用位运算表示状态（如棋盘覆盖问题）。

4.2 状态转移优化

• 单调队列优化：适用于转移方程中存在区间最大值/最小值的情况（如滑动窗口最大值）。
• 四边形不等式优化：用于优化区间DP的时间复杂度。

五、动态规划的实践建议

1. 明确问题边界：确定问题的初始条件（如dp[0][0]的值）。
2. 画状态转移图：通过图示理解子问题间的依赖关系。
3. 调试技巧：
   • 打印DP数组中间结果。
   • 对比递归与迭代结果的一致性。
4. 性能分析：记录DP数组的大小和计算次数，避免指数级复杂度。

六、动态规划的局限性

• 状态爆炸：当状态维度过高时（如超过4维），可能面临内存和计算瓶颈。
• 难以建模：部分问题（如NP难问题）无法用多项式时间的DP解决。

七、总结与扩展

动态规划通过存储子问题解显著提升了算法效率，其关键在于合理定义状态和推导转移方程。开发者可通过LeetCode等平台练习经典DP问题（如70.爬楼梯、322.零钱兑换、518.完全平方数），逐步掌握从一维到多维的DP建模能力。未来可进一步研究近似动态规划（如强化学习中的Q-learning）和并行动态规划（利用GPU加速大规模DP计算）。