数据结构与算法 / 系统课时

自底向上动态规划

自底向上动态规划

记忆化搜索从目标状态向下递归,而自底向上动态规划先计算最小状态,再按依赖顺序逐步得到目标答案。本课通过零钱兑换问题掌握状态定义、初始化和迭代顺序。

学习目标

  • 根据状态依赖确定正确的填表顺序。
  • 将递归状态转移改写为迭代循环,并处理不可达状态。
  • 分析一维动态规划的时间复杂度和空间复杂度。

核心原理

自底向上动态规划先列出全部状态,再保证每个状态在被使用前已经计算完成。对于零钱兑换问题,令 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 或业务约定的失败结果。

本课总结

  • 自底向上动态规划先确定状态依赖,再选择保证前驱已完成的计算顺序。
  • 正确初始化基础状态和不可达状态,是状态转移可靠执行的前提。
  • 总成本等于状态数量乘以每个状态的转移次数,迭代写法不需要递归栈。

下一课预告

后续将继续学习动态规划中的状态压缩、路径还原与多维状态设计,重点判断哪些历史状态必须保留。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

自底向上动态规划

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通