518.零钱兑换2

2024-09-05 02:36
文章标签 兑换 零钱 518

本文主要是介绍518.零钱兑换2,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

518.零钱兑换2

给你一个整数数组 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

思路

基于前面的01背包问题,用了最笨的一种方法来解决问题,在01背包基础上,遍历背包容量时倒序遍历,并构造了while循环来改变当前coin的使用数量,递推公式为dp[j]=dp[j]+dp[j-coins[i]*t];

上述方法复杂度较高。题解的遍历顺序为从前到后,解决了不同数量当前coin的问题。详见代码部分。

ps1:出现这种问题是对滚动数组的01背包问题和完全背包问题理解不到位。在前者是物品只能使用一次,因此需从后遍历背包大小,保证物品使用一次;而完全背包问题则没有这个限制,从前遍历便于涵盖物品多次使用的问题。
ps2:本题 dp[0]=1说明了一种情况:如果正好选了coins[i]后,也就是j-coins[i] == 0的情况表示这个硬币刚好能选,此时dp[0]为1表示只选coins[i]存在这样的一种选法。 也即通过(再次)额外增加当前coin的数值刚好能够有一种新的解法。

代码

    public int change(int amount, int[] coins) {int [] dp=new int[amount+1];dp[0]=1;for (int i=0;i<coins.length;i++){for (int j=amount;j>=coins[i];j--){int t=1;while (j>=coins[i]*t){dp[j]=dp[j]+dp[j-coins[i]*t];t++;}}}return dp[amount];}
    public int change(int amount, int[] coins) {int [] dp=new int[amount+1];dp[0]=1;for (int i=0;i<coins.length;i++){for (int j = coins[i]; j <= amount; j++){dp[j]=dp[j]+dp[j-coins[i]];}}return dp[amount];}

这篇关于518.零钱兑换2的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1137730

相关文章

代码随想录训练营day37|52. 携带研究材料,518.零钱兑换II,377. 组合总和 Ⅳ,70. 爬楼梯

52. 携带研究材料 这是一个完全背包问题,就是每个物品可以无限放。 在一维滚动数组的时候规定了遍历顺序是要从后往前的,就是因为不能多次放物体。 所以这里能多次放物体只需要把遍历顺序改改就好了 # include<iostream># include<vector>using namespace std;int main(){int n,m;cin>>n>>m;std::vector<i

代码随想录算法训练营Day37|完全背包问题、518.零钱兑换II、377. 组合总和 Ⅳ、70. 爬楼梯(进阶版)

完全背包问题                  和01背包最大区别就是一个物品可以重复放多次,因此遍历空间时可以从前往后。 import java.util.*;public class Main{public static void main (String[] args) {Scanner sc = new Scanner(System.in);int m = sc.nextInt

代码随想录:322. 零钱兑换

322. 零钱兑换 class Solution {public:int coinChange(vector<int>& coins, int amount) {vector<int> dp(10005,INT_MAX);//由于后面要取最小值,所以初始大一些dp[0]=0;//总金额为0个数一定为0for(int i=0;i<coins.size();i++){for(int j=coins

微信支付商家转账到零钱:快速开通攻略及功能全解

一、申请资格与条件 哪些商家可以申请商家转账到零钱功能? 仅公司性质的商户可以申请,个体工商户当前不支持此功能。商户账号应无正在进行的处罚,且历史无风险行为。微信支付账户没有历史违规记录。商家系统已经上线并可以访问。是否需要满足开通满90天和连续交易30天的要求? 目前商家转账到零钱及现金红包功能已取消该限制,新注册公司可直接申请,无需等待。 二、申请流程 如何申请开通商家转账到零钱功能

LeetCode 算法:零钱兑换 c++

原题链接🔗:零钱兑换难度:中等⭐️⭐️ 题目 给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。 你可以认为每种硬币的数量是无限的。 示例 1: 输入:coins = [1, 2, 5], amount = 11 输出:3 解释:11 =

硬币兑换

小P的故事——神奇的换零钱 Time Limit: 1000ms   Memory limit: 65536K  有疑问?点这里^_^ 题目描述 已知A国经济很落后,他们只有1、2、3元三种面值的硬币,有一天小P要去A国旅行,想换一些零钱,小P很想知道将钱N兑换成硬币有很多种兑法,但是可惜的是他的数学竟然是体育老师教的,所以他不会啊、、、他只好求助于你,你可以帮他解决吗?

518.零钱兑换Ⅱ

给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。  题目数据保证结果符合 32 位带符号整数。 class Solution{public int change(int amount, int[] coins){// 从coin

代码随想录训练营 Day38打卡 动态规划 part06 322. 零钱兑换 279. 完全平方数 139. 单词拆分

代码随想录训练营 Day38打卡 动态规划 part06 一、力扣322. 零钱兑换 给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。 你可以认为每种硬币的数量是无限的。 示例: 输入:coins = [1, 2, 5], amount = 1

【代码随想录训练营第42期 Day38打卡 - 动态规划Part6 - LeetCode 322. 零钱兑换 279.完全平方数 139.单词拆分

目录 一、做题心得 二、题目与题解 题目一:322. 零钱兑换 题目链接 题解:动态规划--完全背包  题目二: 279.完全平方数 题目链接 题解:动态规划--完全背包 题目三:139.单词拆分 题目链接 题解:动态规划--完全背包 三、小结 一、做题心得 今天来到了代码随想录动态规划章节的Part6,依旧是完全背包问题的应用。相对于前边直接套用模板,今天

外币兑换

题目描述 小明刚从美国回来,发现手上还有一些未用完的美金,于是想去银行兑换成人民币。可是听说最近人民币将会升值,并从金融机构得到了接下来十二个月可能的美元对人民币汇率,现在,小明想要在接下来一年中把美金都兑换成人民币,请问最多能得到多少人民币? 输入格式 输入的第一行是一个实数N(1.00<=N<=100.00),表示小明现有的美金数量。 接下来一行,包含12个实数ai,表示接下来十