LeetCode 动态规划之零钱兑换 II

简介: LeetCode 动态规划之零钱兑换 II

题目


零钱兑换 II


给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。


假设每一种面额的硬币有无限个。


题目数据保证结果符合 32 位带符号整数。


示例 1:


输入:amount = 5, coins = [1, 2, 5]
输出:4
解释:有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1


示例 2:


输入:amount = 3, coins = [2]
输出:0
解释:只用面额 2 的硬币不能凑成总金额 3 。
示例 3:
输入:amount = 10, coins = [10] 
输出:1


题解


解题分析


解题思路:


  1. 最长公共子序列问题是典型的二维动态规划问题。


  1. 题目复述:本题目中给定总金额为 amount, 和数组 coins, 要求计算金额只和等于 amount 的硬币组合数。其中,coins 中的美俄元素可以选取多次,不考虑元素的顺序,因此这个题目是需要计算硬币选取的组合数


  1. 题目分析:我们可以通过动态规划的的方式来计算组数数。用 dp[x] 来表示金额只喝等于 x 的组合数,然后求出 dp[amount] .


  • 动态规划的边界值 dp[0] = 1. 只有当不选择任何硬币的时候,金额之和才为 0 , 因此只有 1种 硬币组合。


  • 对于面额为 coin 的硬币,只有当 coin <= i <= annont 的时候,如果存在一种硬币组合的金额只和等于 i - coin , 则在该硬币组合中增加一个面额的硬币 coin 的硬币,即可以得到一种金额只和等于 i 的硬币组合。因此需要遍历 coins 对于每一种面额的硬币。,更新数组 dp 中每个大雨或者等于该面额的元素的值。


  • 总结动态规划的流程


 1). 初始化 dp[0]  =1;


 2). 遍历 coins, 对于其中的每个元素 coin, 进行如下操作: - 遍历 i 从 coin 到 amount , 将 dp[i-coin] 的值累加到 dp[i]


 3). 最终得到 dp[amount] 的值。


  1. 思考和注意:对于上面的流程是否会存在重复计算的问题。不会, 因为外层循环的遍历的是 coins 的值,内层循环是遍历 不同的金额只和,在计算 dp[i] 的值时,可以确保金额只和 i 的涮许,由于顺序确定,因此不会存在重复的排列。


复杂度:


时间复杂度: O(M*N)


空间复杂度: O(M)


解题代码


题解代码如下(代码中有详细的注释说明):


int change(int amount, int* coins, int coinsSize){
        // 数组
        int dp[amount +1];
        // 数组初始化
        memset(dp, 0, sizeof(dp));
        // 初始化第一个值
        dp[0] = 1;
        // 所有的零钱
        for (int i = 0; i < coinsSize; i++) {
               // 零钱组合
               for (int j = coins[i]; j <= amount; j++) { 
                   dp[j] += dp[j - coins[i]];
               }
        }
        return dp[amount];
}


提交后反馈结果(由于该题目没有进行优化,性能一般):


image.png


参考信息




相关文章
|
3月前
|
Python
【Leetcode刷题Python】518. 零钱兑换 II
解决LeetCode上518题“零钱兑换 II”的Python代码示例,采用动态规划方法计算构成给定总金额的不同硬币组合数。
31 2
|
5月前
|
机器学习/深度学习 存储 算法
LeetCode 题目 95:从递归到动态规划实现 不同的二叉搜索树 II
LeetCode 题目 95:从递归到动态规划实现 不同的二叉搜索树 II
|
3月前
|
Python
【Leetcode刷题Python】322. 零钱兑换
使用动态规划解决LeetCode上322题“零钱兑换”的Python代码示例,目的是计算构成给定金额所需的最少硬币数量。
31 2
【Leetcode刷题Python】322. 零钱兑换
|
5月前
|
缓存
力扣每日一题 6/14 动态规划+数组
力扣每日一题 6/14 动态规划+数组
34 1
|
5月前
|
存储 算法 数据可视化
深入解析力扣161题:相隔为 1 的编辑距离(逐字符比较与动态规划详解)
深入解析力扣161题:相隔为 1 的编辑距离(逐字符比较与动态规划详解)
|
5月前
|
存储 算法 数据可视化
LeetCode 题目 96:从动态规划、递归到卡塔兰数实现不同的二叉搜索树
LeetCode 题目 96:从动态规划、递归到卡塔兰数实现不同的二叉搜索树
|
5月前
|
存储 算法 数据可视化
LeetCode 132题详解:使用动态规划与中心扩展法解决分割回文串 II 的最少分割次数问题
LeetCode 132题详解:使用动态规划与中心扩展法解决分割回文串 II 的最少分割次数问题
|
5月前
|
存储 算法 数据可视化
LeetCode 131题详解:高效分割回文串的递归与动态规划方法
LeetCode 131题详解:高效分割回文串的递归与动态规划方法
|
5月前
|
存储 SQL 算法
优化解码方法:记忆化搜索和空间优化动态规划的实用指南 【LeetCode 题目 91】
优化解码方法:记忆化搜索和空间优化动态规划的实用指南 【LeetCode 题目 91】
|
5月前
|
算法 索引
力扣每日一题 6/28 动态规划/数组
力扣每日一题 6/28 动态规划/数组
49 0