编辑“︁动态规划基础”︁

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

== 核心思想 ==  
动态规划的核心思想包含以下三个关键部分：  
# '''重叠子问题'''：问题可以被分解为若干子问题，且这些子问题会被多次重复计算。  
# '''最优子结构'''：问题的最优解包含其子问题的最优解。  
# '''记忆化存储'''：通过存储子问题的解（通常使用数组或哈希表），避免重复计算。  

动态规划通常有两种实现方式：  
* '''自顶向下'''（Top-down）：递归+记忆化（如带缓存的递归）。  
* '''自底向上'''（Bottom-up）：迭代+表格填充（如二维数组递推）。  

== 基本步骤 ==  
解决动态规划问题的一般步骤如下：  
# 定义子问题（明确状态表示）。  
# 确定状态转移方程（递推关系）。  
# 初始化边界条件。  
# 计算顺序（自顶向下或自底向上）。  
# 返回最终解。  

== 经典示例：斐波那契数列 ==  
斐波那契数列是理解动态规划的经典案例。其定义为：  
<math>F(n) = F(n-1) + F(n-2), \quad F(0)=0, F(1)=1</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):  
    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]  
</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] = \max(dp[i-1][j], dp[i-1][j-w_i] + v_i)  
</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] = 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]  
</syntaxhighlight>  

=== 示例分析 ===  
输入：  
* <code>W = 4</code>, <code>wt = [1, 2, 3]</code>, <code>val = [10, 15, 40]</code>, <code>n = 3</code>  
输出：<code>50</code>（选择物品1和3）  

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

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

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

<mermaid>  
graph LR  
A[原问题] --> B[分解子问题]  
B --> C{是否重叠?}  
C -->|是| D[动态规划]  
C -->|否| E[分治法]  
D --> F[记忆化存储]  
F --> G[组合子问题解]  
G --> H[最终解]  
</mermaid>

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:算法基础]]