自底向上法（动态规划）

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

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

自底向上法的核心是：

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

数学表达为： $d p [i] = F (d p [i - 1], d p [i - 2], \dots)$ 其中 $F$ 表示状态转移方程。

与自顶向下法的对比[编辑 | 编辑源代码]

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

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

问题描述[编辑 | 编辑源代码]

计算第 $n$ 个斐波那契数： $F (n) = {\begin{cases} 0 & n = 0 \\ 1 & n = 1 \\ F (n - 1) + F (n - 2) & n > 1 \end{cases}$

自底向上实现[编辑 | 编辑源代码]

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

空间优化[编辑 | 编辑源代码]

观察到只需前两个状态：

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

实际应用：零钱兑换[编辑 | 编辑源代码]

问题描述[编辑 | 编辑源代码]

给定硬币面额 $c o i n s = [c_{1}, c_{2}, \dots, c_{m}]$ 和目标金额 $a m o u n t$ ，求凑成金额的最少硬币数。

解法[编辑 | 编辑源代码]

定义 $d p [i]$ 为金额 $i$ 的最小硬币数： 解析失败 (语法错误): {\displaystyle dp[i] = \min_{\substack{c \in coins \\ i \geq c}}(dp[i - c] + 1) }

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

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)