【Hot 100 刷题计划】 LeetCode 322. 零钱兑换 | C++ 动态规划 (完全背包极客写法)

LeetCode 322. 零钱兑换 题目描述题目级别中等给你一个整数数组coins表示不同面额的硬币以及一个整数amount表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额返回-1。你可以认为每种硬币的数量是无限的。示例 1:输入coins [1, 2, 5],amount 11输出3解释11 5 5 1示例 2:输入coins [2],amount 3输出-1 破题思路完全背包求最小值这道题是极度经典的“完全背包”问题背包总容量总金额amount。物品重量硬币的面额coins[i]。物品价值1 个硬币我们的目标是让价值/个数总和最小。使用限制每种硬币可以无限次使用。状态定义定义dp[j]为凑成总金额j所需要的最少硬币个数。状态转移方程对于当前的金额j我们可以选择不用当前硬币也可以选择用 1 个当前硬币前提是j coins[i]。如果用当前硬币那么状态就可以由金额为j - coins[i]的最少硬币数加上 1即当前这枚硬币转移而来。我们取所有可能中的最小值dp[j] min(dp[j], dp[j - coins[i]] 1)本解法高光点0x3f3f3f3f 初始化在求最小值时未计算过的状态通常被初始化为无穷大。很多初学者使用INT_MAX但在执行dp[j - coins[i]] 1时极其容易引发INT_MAX 1的整数溢出报错。本解法使用了算法竞赛中极其经典的0x3f3f3f3f来代替无穷大。它是一个大约十亿10910^9109的巨大正数既能保证充当“无穷大”去过滤无效状态又能保证在加 1 时绝对不会超过int的上限是一种非常高级且优雅的技巧 C 代码实现 (完全保留版)classSolution{public:intcoinChange(vectorintcoins,intamount){// 使用变长数组开辟空间 (注: 在部分严苛的 C 标准中建议改为 vectorint dp(amount 10))intdp[amount10];// 极客初始化使用 0x3f3f3f3f 作为无穷大防止后续 1 发生溢出memset(dp,0x3f3f3f3f,sizeofdp);// 凑成金额 0 不需要任何硬币dp[0]0;// 外层循环遍历物品 (各种面额的硬币)for(inti0;icoins.size();i){// 内层循环正序遍历背包容量 (金额)// 完全背包的精髓正序遍历 j使得同一枚硬币可以被重复计算累加for(intjcoins[i];jamount;j){// 状态转移取当前值 与 回头找剩余金额加一枚硬币的较小值dp[j]min(dp[j],dp[j-coins[i]]1);}}// 如果最终金额仍为 0x3f3f3f3f说明没有任何一种组合能凑齐返回 -1returndp[amount]0x3f3f3f3f?-1:dp[amount];}};