力扣HOT100（50）动态规划-零钱兑换

动态规划核心思路一句话讲透用dp[i]表示凑成金额 i 所需的最少硬币个数。 对于每个金额i我们可以尝试使用每一种硬币如果硬币面额coin i那么我们可以用这个硬币剩下的金额就是i - coin凑成i的最少硬币数 凑成i - coin的最少硬币数 1当前这个硬币我们在所有可能的硬币中取硬币数最少的那个所以状态转移方程plaintextdp[i] min(dp[i], dp[i - coin] 1) 当 coin i 时三、完整解题步骤1. 处理边界情况如果amount 0直接返回0如果coins为空且amount 0直接返回-12. 初始化 dp 数组数组长度为amount 1因为要凑 0 到 amount 共 amount1 个金额所有元素初始化为一个不可能达到的大值amount 1为什么用amount 1因为最多需要amount个 1 元硬币所以amount 1是一个永远不可能达到的数用来表示 “这个金额暂时无法凑成”不要用INT_MAX否则dp[i - coin] 1会溢出dp[0] 0凑成 0 元需要 0 个硬币这是所有推导的基础3. 遍历计算 dp 数组外层循环遍历所有金额从1到amount内层循环遍历所有硬币面额如果当前硬币面额coin i可以用这个硬币按照状态转移方程更新dp[i]dp[i] min(dp[i], dp[i - coin] 1)4. 结果判断如果dp[amount] amount说明这个金额无法凑成返回-1否则返回dp[amount]class Solution { public: int coinChange(vectorint coins, int amount) { int Max amount1;//因为待会要比较最小值 所以初始化尽可能大最大面值是amount所以amount不可能达到 vectorint dp(amount 1,Max);//长度amount1所有值初始化为amount1 dp[0] 0; for(int i 1;i amount;i){//遍历面额的所有构成 比如11块1块、2块 for(int j 0;j(int)coins.size();j){//遍历所有的硬币 if(coins[j]i){//如果这个硬币面额比当前面额小 才能用 //当前这个面额等于下面的公式 dp[i] min(dp[i],dp[i-coins[j]]1); //总硬币数 凑i-coin的硬币数 1 。这个就是先用这个小额的硬币一次然后再和 当前面额-硬币面额 需要的数量求和。 } } } return dp[amount] amount ? -1:dp[amount];//判断是否满足如果最后的数量大于amount凑不出来因为最大就是和amount数量一样的一块钱构成的。满足条件就返回 } };