编辑“︁动态规划”︁

{{DISPLAYTITLE:动态规划}}  
'''动态规划'''（Dynamic Programming，简称DP）是一种用于解决复杂问题的算法设计技术，通过将问题分解为相互重叠的子问题，并存储子问题的解以避免重复计算，从而提高效率。动态规划常用于优化问题，如最短路径、背包问题、序列对齐等。  

== 基本概念 ==  
动态规划的核心思想包括以下两点：  
# '''重叠子问题'''：问题可以被分解为多个相似的子问题，这些子问题会被重复计算。  
# '''最优子结构'''：问题的最优解可以通过子问题的最优解组合得到。  

动态规划通常有两种实现方式：  
* '''自顶向下（记忆化搜索）'''：从原问题出发，递归地解决子问题，并使用表格（如数组或哈希表）存储已计算的子问题结果。  
* '''自底向上（迭代法）'''：从最小的子问题开始，逐步构建更大问题的解，通常使用表格填充法。  

== 动态规划步骤 ==  
解决动态规划问题的一般步骤如下：  
# 定义状态：明确问题的子问题，并用变量表示状态。  
# 确定状态转移方程：描述如何从一个或多个子问题的解得到当前问题的解。  
# 初始化边界条件：确定最小子问题的解。  
# 计算顺序：确定填表的顺序（自底向上或自顶向下）。  
# 返回最终解：通常存储在表格的某个特定位置。  

== 经典示例：斐波那契数列 ==  
斐波那契数列是动态规划的经典入门问题，定义为：  
<math>F(n) = \begin{cases}  
0 & \text{if } n = 0, \\  
1 & \text{if } n = 1, \\  
F(n-1) + F(n-2) & \text{if } n > 1.  
\end{cases}</math>  

=== 递归解法（低效） ===  
直接递归会导致大量重复计算，时间复杂度为<math>O(2^n)</math>：  
<syntaxhighlight lang="python">  
def fib(n):  
    if n <= 1:  
        return n  
    return fib(n-1) + fib(n-2)  
</syntaxhighlight>  

=== 动态规划解法（高效） ===  
使用动态规划存储中间结果，时间复杂度降为<math>O(n)</math>：  
<syntaxhighlight lang="python">  
def fib(n):  
    if n <= 1:  
        return n  
    dp = [0] * (n + 1)  
    dp[1] = 1  
    for i in range(2, n + 1):  
        dp[i] = dp[i-1] + dp[i-2]  
    return dp[n]  
</syntaxhighlight>  

=== 输入输出示例 ===  
输入：<code>n = 5</code>  
输出：<code>5</code>（因为斐波那契数列为0, 1, 1, 2, 3, 5）  

== 实际案例：背包问题 ==  
'''0-1背包问题'''是动态规划的典型应用：给定一组物品，每个物品有重量<math>w_i</math>和价值<math>v_i</math>，在背包容量限制<math>W</math>下，如何选择物品使总价值最大？  

=== 状态定义与转移方程 ===  
定义<math>dp[i][j]</math>为前<math>i</math>个物品在容量<math>j</math>下的最大价值。状态转移方程为：  
<math>  
dp[i][j] = \begin{cases}  
dp[i-1][j] & \text{if } w_i > j, \\  
\max(dp[i-1][j], dp[i-1][j-w_i] + v_i) & \text{otherwise.}  
\end{cases}  
</math>  

=== 代码实现 ===  
<syntaxhighlight lang="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], dp[i-1][j-wt[i-1]] + val[i-1])  
    return dp[n][W]  
</syntaxhighlight>  

=== 输入输出示例 ===  
输入：<code>W = 5, wt = [2, 3, 4], val = [3, 4, 5], n = 3</code>  
输出：<code>7</code>（选择物品1和物品2，总重量5，价值7）  

== 动态规划优化 ==  
动态规划的空间复杂度通常可以优化。例如，斐波那契数列只需两个变量存储前两个状态：  
<syntaxhighlight lang="python">  
def fib(n):  
    a, b = 0, 1  
    for _ in range(n):  
        a, b = b, a + b  
    return a  
</syntaxhighlight>  

背包问题可以优化为一维数组：  
<syntaxhighlight lang="python">  
def knapsack(W, wt, val, n):  
    dp = [0] * (W + 1)  
    for i in range(n):  
        for j in range(W, wt[i] - 1, -1):  # 逆向遍历避免重复计算  
            dp[j] = max(dp[j], dp[j - wt[i]] + val[i])  
    return dp[W]  
</syntaxhighlight>  

== 应用场景 ==  
动态规划广泛用于以下领域：  
* 序列问题（最长公共子序列、编辑距离）  
* 图问题（最短路径、Floyd-Warshall算法）  
* 资源分配（背包问题、股票买卖问题）  
* 字符串处理（正则表达式匹配）  

== 总结 ==  
动态规划通过存储子问题的解避免重复计算，显著提高算法效率。掌握动态规划的关键在于：  
# 识别重叠子问题和最优子结构。  
# 设计正确的状态表示和转移方程。  
# 选择适当的实现方式（自顶向下或自底向上）。  

通过练习经典问题（如斐波那契数列、背包问题）和实际案例，可以逐步掌握动态规划的核心思想与应用技巧。

[[Category:计算机科学]]
[[Category:面试技巧]]
[[Category:算法基础]]