给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，求组成aim的最少货币数。
如果无解，请返回-1.
数据范围：数组大小满足 
， 数组中每个数字都满足 
，
要求：时间复杂度 )
，空间复杂度 )
。
[编程题]兑换零钱(一)
精华题解
题目主要信息：
给定数组arr，arr中所有的值都为正整数且不重复
arr中每个值代表一种面值的货币，每种面值的货币可以使用任意
组成aim的最少货币数
如果无解，请返回-1
举一反三：
本题属于背包问题的一种简化版本，学习完本题的思路帮助你解决相似的背包问题。
方法一：动态规划（推荐使用）
知
展开全文
- 1、题目描述： - 2、题目链接： https://www.nowcoder.com/practice/3911a20b3f8743058214ceaa099eeb45?tpId=196&&tqId=37128&rp=1&ru=/activity/oj&q
展开全文
就拿给定的例子来说，有5，2，3，三种面值的钱，现在拿出一张20元的，怎么兑换才能使钱的张数最少。
首先，我们知道可兑换的钱的最大张数是20，也就是面值是1的时候，其他可兑换的情况张数肯定小于20，那么可兑换张数<=20才是可考虑的范围，且要求最小值。
设置的计数数组的
展开全文
换钱的最少货币数 题目链接 Solution 问n种货币凑成一个面额所需要的最少货币数。动态规划。 表示凑成面额i的需要的最少货币数。然后枚举每个面额的货币，更新dp数组即可。 Code class Solution {
public:
int minMoney(vector<int
展开全文
兑换零钱(一)
描述
给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，求组成aim的最少货币数。
如果无解，请返回-1.
数据范围：数组大小满足 0≤n≤10000 ， 数组中每个数字都满足 0<va
展开全文
有点难理解，其实还是递归，https://www.jianshu.com/p/b9d7ff91684e i: 代表可以使用的货币种类为 arr[0..i]j: 代表需要兑换的面值数，其取值范围为[0..aim]，因此实现时，二维数组的列数应该为aim + 1对于dp[i][j]，更新的依据有两个值
展开全文
C++
动态规划问题
要点：
dp[j] = min(dp[j], dp[j - arr[i]] + 1);
dp[0] = 0;
int dp[aim + 1];
dp[0] = 0;
for (int i = 1; i <= aim; ++i) dp[i] = IN
展开全文
public class Solution {
/**
* 最少货币数
* @param arr int整型一维数组 the array
* @param aim int整型 the target
* @return int整型
*/
展开全文
简单的动态规划思想
class Solution:
def minMoney(self , coins: List[int], amount: int) -> int:
dp=[float('inf')]*(amount+1)
dp[0]=0
展开全文
完全背包变形
dp[i][v]: 用前i个硬币组合出价值v所需的最少硬币数
dp[0][0]=1, dp[0][v]=0 for v>0.
dp[i][v] = Min {
(a) dp[i-1][v], // 不用i硬币
(b) dp[i][v-arr[i]] // 用i
展开全文
问题信息
难度：
119条回答
1155收藏
6470浏览
通过挑战的用户
查看代码-
2022-10-26 20:19:52
-
2022-10-10 20:56:54
-
2022-09-16 16:40:28
-
2022-09-16 15:48:40 -
2022-09-16 15:01:37
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
