用内网穿透做网站可以被收录吗,成都鱼羊环保网站制作设计,品牌建设的建议,最新网站开发语言518. 零钱兑换Ⅱ
题目链接#xff1a;力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台
思路
本题相当于求装满容量为amount的背包有多少种方法#xff0c;又由于零钱可以重复使用#xff0c;属于完全背包的题型。将01背包完全装满的思路在494. 目…518. 零钱兑换Ⅱ
题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
思路
本题相当于求装满容量为amount的背包有多少种方法又由于零钱可以重复使用属于完全背包的题型。将01背包完全装满的思路在494. 目标和中介绍过在完全背包的理论基础中知道它与01背包的接替区别只在于遍历顺序因此此题很容易便能写出。代码随想录算法训练营第四十八天动态规划篇之01背包| 1049. 最后一块石头的重量Ⅱ494. 目标和-CSDN博客代码随想录算法训练营第四十九天动态规划篇| 474. 一和零 完全背包理论基础-CSDN博客
1. dp数组定义
dp[j]装满容量为j的完全背包有dp[j]种方法。
2. 递推公式
对于面值为i的零钱它和之前遍历过的零钱凑成总金额amount的方法取决于之前的硬币能凑成总金额(amount-i)的方法把这个零钱i能凑成的方法加入到dp[j]中。因此递推公式为
dp[j] dp[amount - i]
3. 初始条件
dp[0]要为1如果是0那么之后递推出来的dp值都为0。dp[0] 1可以认为凑成零就是不拿出任何零钱这一种方法。dp[0]1还说明了一种情况如果正好选了面值为j的零钱也就是j-coins[i] 0的情况表示这个硬币刚好能选此时dp[0]为1表示只选coins[i]存在这样的一种选法。其他下标的dp值保持为0就可。
4. 遍历顺序
对完全背包求总和的最大价值容量从小到大遍历可以外层遍历物体内层遍历容量也可以外层遍历容量内层便遍历物体和凑成总和的元素有没有顺序没关系。但对于这道题我们要求凑成总和的元素是无序的即{14}和{41}都能凑成5但它们是一种方法而非两种。分别考虑两种遍历顺序
1. 外层遍历容量内层遍历物体
如果先遍历容量再遍历物体对当前容量假设遍历第一个物体发现与第三个物体能凑成总和方法数加了1那继续遍历到第三个物体时又发现能与第一个物体凑成方法数又加了1就重复了。
2. 外层遍历物体内层遍历容量
如果先遍历物体再遍历容量就是先把第一个物体加入运算那时第三个物体还没加入所以没有凑成等遍历到第三个物体时才能和第一个物体凑成不会造成重复。
因此应该外层遍历物体内层遍历容量。
5. 举例推导dp数组
输入: amount 5, coins [1, 2, 5] dp状态图如下 代码实现
class Solution(object):def change(self, amount, coins):dp [0]*(amount 1)dp[0] 1for coin in coins: for j in range(coin, amount 1):dp[j] dp[j-coin]return dp[amount]
