[编程题]换钱的最少货币数
- 热度指数：8787 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，求组成aim的最少货币数。
输入描述:
输入包括两行，第一行两个整数n（0<=n<=1000）代表数组长度和aim（0<=aim<=5000），第二行n个不重复的正整数，代表arr。
输出描述:
输出一个整数，表示组成aim的最小货币数，无解时输出-1.
示例1
输入
3 20 5 2 3
输出
4
说明
20=5*4
示例2
输入
3 0 5 2 3
输出
0
示例3
输入
2 2 3 5
输出
-1
备注:
时间复杂度，空间复杂度
。
表示组成 价值需要的最少的货币数如果目前情况下价值目前最少能由 个货币组成，那么加了一个 价值的商品，就可以由个货币组成对于每一个物品，从循环一遍，更新dp的值。所有的物品都加入完毕以后，就是结果。 #include<iostream>
using namespace std;
co
展开全文
入门动态规划 import java.io.*;
import java.util.Arrays;
public class Main{
public static void main(String[] args) throws IOException{
BufferedRe
展开全文
#include<iostream>
#include<vector>
using namespace std;
int minCoin(vector<int>& n,int aim){
//dp[N][0]表示，当所有的面额全部试完之后，并且a
展开全文
思路：动态规划，建立aim+1位的数组f，f[i]表示i元所需最小张数。初始都赋值为-1，0位置的值为0.进行动态规划，对于每一个位置i，遍历面值数组，i减去面值在f数组范围内且可达(即f对应位置不为-1)则更新数组f。
#include <iostream>
#include <
展开全文
动态规划，建立一个辅助数组dp，记录花i块钱要用的最少张数，每次输入一个arr，就将dp[arr]设置为1，然后从arr+1到aim开始更新数组dp，方程为dp[j] = min(dp[j], dp[j-arr]+1);代码如下： #include<bits/stdc++.h>
#def
展开全文
l, target = map(int, input().split())
cash = list(map(int, input().split()))
dp = [float("inf")] * (target + 1)
dp[0] = 0
for i in range(1, target + 1
展开全文
方法一
参考动态规划的意义是什么？ - 阮行止的回答中1. 从一个生活问题谈起的思路。
#include<iostream>
#include<vector>
using namespace std;
int getMinCoin(vector<int>&am
展开全文
暴力效率较低，而且需要循环计算知道找到有解的情况，下面只是个错误的例子 def solve(l, n, k):
if n < 1:
return 0
count = 0
for i in l:
count += k//i
展开全文
package main
import (
"fmt"
)
func main() {
num, target := 0, 0
for {
n, _ := fmt.Scan(&num, &target)
展开全文
问题信息
通过挑战的用户
查看代码-
2022-12-19 23:04:22
-
2022-12-03 20:12:43 -
2022-09-12 01:26:56
-
2022-09-11 17:46:36 -
2022-09-09 19:47:21
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
