动态规划基础

动态规划（Dynamic Programming，简称DP）是一种用于解决复杂问题的算法设计技术，通过将问题分解为相互重叠的子问题，并存储子问题的解以避免重复计算，从而提高效率。动态规划广泛应用于优化问题、组合数学、经济学等领域。

核心思想[编辑 | 编辑源代码]

动态规划的核心思想包含以下三个关键部分：

重叠子问题：问题可以被分解为若干子问题，且这些子问题会被多次重复计算。
最优子结构：问题的最优解包含其子问题的最优解。
记忆化存储：通过存储子问题的解（通常使用数组或哈希表），避免重复计算。

动态规划通常有两种实现方式：

自顶向下（Top-down）：递归+记忆化（如带缓存的递归）。
自底向上（Bottom-up）：迭代+表格填充（如二维数组递推）。

基本步骤[编辑 | 编辑源代码]

解决动态规划问题的一般步骤如下：

定义子问题（明确状态表示）。
确定状态转移方程（递推关系）。
初始化边界条件。
计算顺序（自顶向下或自底向上）。
返回最终解。

经典示例：斐波那契数列[编辑 | 编辑源代码]

斐波那契数列是理解动态规划的经典案例。其定义为： $F (n) = F (n - 1) + F (n - 2), F (0) = 0, F (1) = 1$

递归解法（低效）[编辑 | 编辑源代码]

直接递归会导致大量重复计算，时间复杂度为 $O (2^{n})$ ：

  
def fib(n):  
    if n <= 1:  
        return n  
    return fib(n-1) + fib(n-2)

动态规划解法[编辑 | 编辑源代码]

通过存储中间结果，将时间复杂度优化至 $O (n)$ ：

  
def fib(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]

输入输出示例[编辑 | 编辑源代码]

输入：n = 5 输出：5（序列：0, 1, 1, 2, 3, 5）

实际案例：背包问题[编辑 | 编辑源代码]

0-1背包问题是动态规划的典型应用。问题描述：

给定一组物品，每个物品有重量 $w_{i}$ 和价值 $v_{i}$ 。
背包容量为 $W$ ，求不超过容量的最大价值。

状态转移方程[编辑 | 编辑源代码]

定义 $d p [i] [j]$ 为前 $i$ 个物品在容量 $j$ 下的最大价值： $d p [i] [j] = \max (d p [i - 1] [j], d p [i - 1] [j - w_{i}] + v_{i})$

代码实现[编辑 | 编辑源代码]

  
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] = max(val[i-1] + dp[i-1][j-wt[i-1]], dp[i-1][j])  
            else:  
                dp[i][j] = dp[i-1][j]  
    return dp[n][W]

示例分析[编辑 | 编辑源代码]

输入：

W = 4, wt = [1, 2, 3], val = [10, 15, 40], n = 3

输出：50（选择物品1和3）

动态规划优化技巧[编辑 | 编辑源代码]

空间优化：某些问题可将二维数组压缩为一维（如背包问题的滚动数组）。
状态压缩：用位运算表示状态（如旅行商问题）。
贪心结合：部分问题可结合贪心策略进一步优化。

常见问题类型[编辑 | 编辑源代码]

线性DP：最长递增子序列、最大子数组和。
区间DP：矩阵链乘法、石子合并。
树形DP：二叉树中的最大路径和。

总结[编辑 | 编辑源代码]

动态规划通过分解问题、存储中间结果显著提升效率。掌握其核心思想和经典模型（如斐波那契、背包问题）是进阶算法学习的关键。