数据结构与算法 / 系统课时
自底向上动态规划
自底向上动态规划
记忆化搜索从目标状态向下递归,而自底向上动态规划先计算最小状态,再按依赖顺序逐步得到目标答案。本课通过零钱兑换问题掌握状态定义、初始化和迭代顺序。
学习目标
- 根据状态依赖确定正确的填表顺序。
- 将递归状态转移改写为迭代循环,并处理不可达状态。
- 分析一维动态规划的时间复杂度和空间复杂度。
核心原理
自底向上动态规划先列出全部状态,再保证每个状态在被使用前已经计算完成。对于零钱兑换问题,令 dp[x] 表示凑出金额 x 所需的最少硬币数。计算 dp[x] 时,需要查看每种硬币 coin 对应的前驱状态 dp[x - coin]。
因为 x - coin 总是小于 x,金额应从小到大遍历。基础状态是 dp[0] = 0,表示凑出金额 0 不需要硬币。其他状态先设为不可达哨兵值,只有存在有效前驱时才更新。

若共有 amount + 1 个金额状态和 m 种硬币,每个状态都检查全部硬币,时间复杂度为 O(amount × m),空间复杂度为 O(amount)。循环顺序不是形式问题;它必须与依赖方向一致,否则可能读取尚未完成的状态。
完整可运行示例
下面的 Java 17 程序构建完整的 dp 数组。将代码保存为 BottomUpCoinChange.java。
java
import java.util.Arrays;
public class BottomUpCoinChange {
private static int[] buildDp(int[] coins, int amount) {
int unreachable = amount + 1;
int[] dp = new int[amount + 1];
Arrays.fill(dp, unreachable);
dp[0] = 0;
// 金额递增,保证 dp[current - coin] 已经计算完成。
for (int current = 1; current <= amount; current++) {
for (int coin : coins) {
if (coin <= current && dp[current - coin] != unreachable) {
dp[current] = Math.min(
dp[current],
dp[current - coin] + 1
);
}
}
}
return dp;
}
public static void main(String[] args) {
int[] coins = {1, 2, 5};
int amount = 11;
int[] dp = buildDp(coins, amount);
int answer = dp[amount] > amount ? -1 : dp[amount];
System.out.println("硬币: " + Arrays.toString(coins));
System.out.println("状态表: " + Arrays.toString(dp));
System.out.println("凑出 " + amount + " 的最少硬币数: " + answer);
}
}编译并运行:
bash
javac BottomUpCoinChange.java
java BottomUpCoinChange预期输出与常见错误
text
硬币: [1, 2, 5]
状态表: [0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3]
凑出 11 的最少硬币数: 3常见错误是把所有 dp 元素初始化为 0,这会让不可达状态看起来像已经得到最优答案。示例使用 amount + 1 作为哨兵,因为凑出金额 amount 最多使用 amount 枚面值为 1 的硬币,任何更大值都可以安全表示不可达。
更新前还要检查前驱状态是否可达,否则哨兵值加 1 可能被当成候选答案。若硬币集合不包含 1,最终 dp[amount] 仍可能是哨兵值,此时应转换为 -1 或业务约定的失败结果。
本课总结
- 自底向上动态规划先确定状态依赖,再选择保证前驱已完成的计算顺序。
- 正确初始化基础状态和不可达状态,是状态转移可靠执行的前提。
- 总成本等于状态数量乘以每个状态的转移次数,迭代写法不需要递归栈。
下一课预告
后续将继续学习动态规划中的状态压缩、路径还原与多维状态设计,重点判断哪些历史状态必须保留。
按自己的节奏,确认真正理解。