编辑“︁自底向上法（动态规划）”︁

{{DISPLAYTITLE:自底向上法（动态规划）}}

'''自底向上法'''（Bottom-Up Approach）是[[动态规划]]中解决子问题依赖关系的核心方法之一，与[[自顶向下法]]（记忆化递归）形成对比。该方法通过从最小子问题开始逐步构建最终解，避免了递归带来的栈开销，通常具有更优的空间效率。

== 核心思想 ==
自底向上法的核心是：
# '''定义基础状态'''：解决最小规模的子问题（通常是递归终止条件）。
# '''递推关系'''：用已解决的子问题结果推导更大规模问题的解。
# '''顺序填充'''：按问题规模从小到大计算并存储结果（通常使用数组或表格）。

数学表达为：
<math>
dp[i] = F(dp[i-1], dp[i-2], \ldots)
</math>
其中<math>F</math>表示状态转移方程。

== 与自顶向下法的对比 ==
{| class="wikitable"
|+ 方法对比
! 特性 !! 自底向上法 !! 自顶向下法
|-
| 计算顺序 || 从小问题到大问题 || 从大问题分解到小问题
|-
| 存储结构 || 通常用数组/矩阵 || 递归调用+记忆化
|-
| 栈空间 || 无递归栈开销 || 可能栈溢出
|-
| 适用场景 || 明确依赖顺序的问题 || 依赖关系复杂的问题
|}

== 经典示例：斐波那契数列 ==
=== 问题描述 ===
计算第<math>n</math>个斐波那契数：
<math>
F(n) = \begin{cases} 
0 & n=0 \\
1 & n=1 \\
F(n-1)+F(n-2) & n>1 
\end{cases}
</math>

=== 自底向上实现 ===
<syntaxhighlight lang="python">
def fibonacci(n):
    if n == 0:
        return 0
    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]

# 示例
print(fibonacci(5))  # 输出: 5
</syntaxhighlight>

=== 空间优化 ===
观察到只需前两个状态：
<syntaxhighlight lang="python">
def fibonacci_optimized(n):
    if n < 2:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b
</syntaxhighlight>

== 实际应用：零钱兑换 ==
=== 问题描述 ===
给定硬币面额<math>coins = [c_1, c_2, \ldots, c_m]</math>和目标金额<math>amount</math>，求凑成金额的最少硬币数。

=== 解法 ===
定义<math>dp[i]</math>为金额<math>i</math>的最小硬币数：
<math>
dp[i] = \min_{\substack{c \in coins \\ i \geq c}}(dp[i - c] + 1)
</math>

=== 代码实现 ===
<syntaxhighlight lang="python">
def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for c in coins:
            if i >= c:
                dp[i] = min(dp[i], dp[i - c] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

# 示例
print(coinChange([1, 2, 5], 11))  # 输出: 3 (5+5+1)
</syntaxhighlight>

== 动态规划表可视化 ==
<mermaid>
graph LR
    A[金额 0] -->|0| B[金额 1]
    B -->|1| C[金额 2]
    C -->|1| D[金额 3]
    D -->|2| E[金额 4]
    E -->|2| F[金额 5]
    F -->|1| G[...]
</mermaid>

== 复杂度分析 ==
* '''时间复杂度'''：通常为<math>O(n \times k)</math>（<math>n</math>为问题规模，<math>k</math>为状态转移成本）
* '''空间复杂度'''：通常为<math>O(n)</math>，可优化到<math>O(1)</math>（如斐波那契数列）

== 适用问题特征 ==
1. '''最优子结构'''：问题的最优解包含子问题的最优解
2. '''无后效性'''：当前状态只与之前状态有关
3. '''重叠子问题'''：子问题被重复计算

== 进阶技巧 ==
* '''滚动数组'''：将空间复杂度从<math>O(n)</math>降至<math>O(1)</math>
* '''维度分解'''：处理多维动态规划时逐维度计算
* '''状态压缩'''：用位运算表示状态（如旅行商问题）

== 常见错误 ==
{{Warning|1=
* 未正确初始化基础状态
* 循环顺序错误（如背包问题中逆序与正序的区别）
* 忽略状态转移的边界条件
}}

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:动态规划]]