[编程题]硬币划分
# python3 def change(coins, n): len1 = len(coins) if len1 == 0 and n < 1 or n > 100000: return None ways = [0] * (n + 1) # 初始化 ways[0] = 1 for i in range(len1): for j in range(coins[i], n + 1): # 保证n小于等于100000，为了防止溢出，请将答案Mod 1000000007 ways[j] = (ways[j] + ways[j - coins[i]]) % 1000000007 print(ways[n]) if __name__ == '__main__': coins, n = [1, 2, 5, 10], int(input()) change(coins, n)
发表于 2019-09-02 21:04:01
回复(2)
#include<iostream>
using namespace std;
int countWays(int n) {
// write code here
int coins[4]={1,2,5,10};
int dp[100001] = {0};
dp[0] = 1;
for(int i = 0;i < 4;++i){
for(int j = coins[i];j <= n;++j){
dp[j] =(dp[j]+dp[j-coins[i]])%1000000007;
}
}
return dp[n];
}
int main()
{
int n;
cin>>n;
cout<<countWays(n)<<endl;
}
using namespace std;
int countWays(int n) {
// write code here
int coins[4]={1,2,5,10};
int dp[100001] = {0};
dp[0] = 1;
for(int i = 0;i < 4;++i){
for(int j = coins[i];j <= n;++j){
dp[j] =(dp[j]+dp[j-coins[i]])%1000000007;
}
}
return dp[n];
}
int main()
{
int n;
cin>>n;
cout<<countWays(n)<<endl;
}
发表于 2019-11-05 19:45:59
回复(0)
#include<iostream>
using namespace std;
int a[4] = { 1,2,5,10 };
int cnt = 0;
int num;
int total = 0;
long long dp[1000001] = {1};
void dfs(int n) {
if (total == num) {
cnt++;
cnt = cnt % (int(1e9 + 7));
return;
}
if (total > num)return;
for (int i = n; i < 4; i++) {
total += a[i];
dfs(i);
total -= a[i];
}
}
void dd(int n) {
for (int i = 0; i < 4; i++) {
for (int j =a[i]; j <=n; j++) {
dp[j] = (dp[j]+dp[j-a[i]]) % 1000000007;
}
}
}
int main() {
cin >> num;
dd(num);
using namespace std;
int a[4] = { 1,2,5,10 };
int cnt = 0;
int num;
int total = 0;
long long dp[1000001] = {1};
void dfs(int n) {
if (total == num) {
cnt++;
cnt = cnt % (int(1e9 + 7));
return;
}
if (total > num)return;
for (int i = n; i < 4; i++) {
total += a[i];
dfs(i);
total -= a[i];
}
}
void dd(int n) {
for (int i = 0; i < 4; i++) {
for (int j =a[i]; j <=n; j++) {
dp[j] = (dp[j]+dp[j-a[i]]) % 1000000007;
}
}
}
int main() {
cin >> num;
dd(num);
cout << dp[num];
return 0;
}
编辑于 2019-09-21 21:46:58
回复(0)
n = int(input()) m = [1] + [0]*n for i in (1,2,5,10): for j in range(i,n+1): m[j] = (m[j] + m[j-i]) % 1000000007 print(m[-1])
发表于 2019-09-17 01:11:20
回复(0)
//C语言编程，使用动态规划，已经通过测试
#include <stdio.h>
#include <string.h>
int coins[4]={1,2,5,10};
long sum=0;
void Div(long n,int m)
{
if(m>2)
{
int k=n/coins[m-1],i;
for(i=0;i<=k;i++)
{
Div(n-i*coins[m-1],m-1);
}
}
else if(m==2)
{
sum=(sum+n/2+1)%(1000000007);
// printf("%ld\n",sum);
}
}
int main()
{
long n;
scanf("%ld",&n);
Div(n,4);
printf("%ld\n",sum);
return 0;
}
#include <stdio.h>
#include <string.h>
int coins[4]={1,2,5,10};
long sum=0;
void Div(long n,int m)
{
if(m>2)
{
int k=n/coins[m-1],i;
for(i=0;i<=k;i++)
{
Div(n-i*coins[m-1],m-1);
}
}
else if(m==2)
{
sum=(sum+n/2+1)%(1000000007);
// printf("%ld\n",sum);
}
}
int main()
{
long n;
scanf("%ld",&n);
Div(n,4);
printf("%ld\n",sum);
return 0;
}
发表于 2019-09-22 22:26:43
回复(0)
import java.util.Scanner;
public class Main {
public static void main(String args[]) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int coins[]= {1,2,5,10};
int [] dp=new int[100001];
dp[0]=1;
for(int i=0;i<4;i++) {
for(int j=coins[i];j<=n;j++) {
dp[j]=(dp[j]+dp[j-coins[i]])%1000000007;
}
}
System.out.println(dp[n]);
}
}
public class Main {
public static void main(String args[]) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int coins[]= {1,2,5,10};
int [] dp=new int[100001];
dp[0]=1;
for(int i=0;i<4;i++) {
for(int j=coins[i];j<=n;j++) {
dp[j]=(dp[j]+dp[j-coins[i]])%1000000007;
}
}
System.out.println(dp[n]);
}
}
发表于 2019-09-03 16:09:27
回复(4)
状态F(i,j) :前i种硬币组成j的方法个数
转移方程：F(i,j): F(i - 1,j) + F(i,j - coins[i - 1]);
初始状态：F(i,0) = 1; F(0,j) = 0;
返回：F(coins,size(),n)
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = {1,2,5,10};
int[][] methodNum = new int[arr.length + 1][n + 1];
for(int i = 0;i <= arr.length;i++){
methodNum[i][0] = 1;
}
for(int i = 1;i <= arr.length;i++){
for(int j = 0;j <= n;j++){
if(j >= arr[i - 1]){
methodNum[i][j] = (methodNum[i - 1][j] + methodNum[i][j - arr[i - 1]]) % 1000000007;
}else{
methodNum[i][j] = methodNum[i - 1][j];
}
}
}
System.out.println(methodNum[arr.length][n]);
}
}
发表于 2022-04-08 15:48:58
回复(0)
n = int(input()) n_5 = n//5 idea = 0 for x in range(n_5+1): idea += (x//2+1)*((n-5*x)//2+1) print(int(idea%(1e9+7)))运行时间： 46 ms 占用内存：3556K
编辑于 2019-09-28 22:30:59
回复(0)
暴力破解
public static void combine(int k)
{
if(k<=0)
return;
int sum=0,i=0,j=0,m=0,n=0,num=0;
for(i=0;i<=k/10;i++)
{
for(j=0;j<=(k-i*10)/5;j++)
{
for(m=0;m<=(k-i*10-j*5)/2;m++)
{
for(n=0;n<=(k-i*10-j*5-m*2);n++)
{
if(k==10*i+5*j+2*m+n)
num++;
}
}
}
}
num=(int) (num%(1e9+7));
System.out.println(num);
}
{
if(k<=0)
return;
int sum=0,i=0,j=0,m=0,n=0,num=0;
for(i=0;i<=k/10;i++)
{
for(j=0;j<=(k-i*10)/5;j++)
{
for(m=0;m<=(k-i*10-j*5)/2;m++)
{
for(n=0;n<=(k-i*10-j*5-m*2);n++)
{
if(k==10*i+5*j+2*m+n)
num++;
}
}
}
}
num=(int) (num%(1e9+7));
System.out.println(num);
}
发表于 2019-09-26 15:30:42
回复(0)
function dealData(n){
var dp=new Array(100001);
for(var k=0;k<dp.length;k++){
dp[k]=0;
}
dp[0]=1;
var coins=[1,2,5,10];
for(var i=0;i<coins.length;i++){
for(var j=coins[i];j<dp.length;j++){
dp[j]=(dp[j]+dp[j-coins[i]])%1000000007
}
}
print(dp[n]);
}
dealData(readline());
为什么在牛客网的编译器上，数组设为n+1不能通过？
发表于 2019-09-22 20:49:39
回复(0)
#include<stdio.h>
#include<math.h>
int main() {
long long n;
long long coins[] = {1,2,5,10};
long long dp[1000001];
long long i, j;
dp[0] = 1;
scanf("%lld", &n);
for (i = 0; i < 4; i++) {
for (j = coins[i]; j <= n; j++) {
dp[j] = (dp[j] + dp[j - coins[i]])%1000000007;
}
}
printf("%lld", dp[n]);
return 0;
} 令f（0） = 1 f(1) = f(1)+f(1-1) f(2) = f(2)+f(2-2)+f(2-1) f(3) = f(3)+f(3-2)+f(3-1) 定义一个数据保存a[1] 表示组成1分钱的种数 a[n] 表示组成n分钱的种数
抄那个java大佬的思路，不会写，只能硬背
发表于 2019-09-09 22:28:02
回复(4)
package Arithmetic;
public class charge_coins2 {
public static void main(String[] args) {
// TODO Auto-generated method stub
//具有的零钱的面值
double[] V = new double[]{1,0.5,0.1,0.05,0.02,0.01};
//需要找的零钱
double money = 1.23;
//返回结果的数组
int [] result = new int[V.length];
result = Greedy(V, money);
for (int i=0;i<result.length;i++){
System.out.println(" "+result[i]);
}
}
static int[] Greedy(double[] V, double money){
//返回结果的数组
int [] result = new int[V.length];
//先对数据进行挑选，先将零钱中面值大于要找的零钱进行剔除
int j=0;
//将挑选的数值进行贪婪最优化
for (int i=0; i<V.length;++i){
//向下取整
if (money>=V[i]){
int number=(int)Math.floor((money*100)/(V[i]*100));
if(money-number*V[i]==0){
result[j]=number;
++j;
break;
}else{
//出现数据泄露，最后money=0.00999999999988
money=money-number*V[i];
result[j]=number;
++j;
}
}else{
result[j]=0;
++j;
}
}
//进行结果反向验证
double sum=0;
for(int i=0; i<V.length;i++){
sum=sum+result[i]*V[i];
}
if (sum!=money){
result[result.length-1]+=1;
}
return result;
}
}
public class charge_coins2 {
public static void main(String[] args) {
// TODO Auto-generated method stub
//具有的零钱的面值
double[] V = new double[]{1,0.5,0.1,0.05,0.02,0.01};
//需要找的零钱
double money = 1.23;
//返回结果的数组
int [] result = new int[V.length];
result = Greedy(V, money);
for (int i=0;i<result.length;i++){
System.out.println(" "+result[i]);
}
}
static int[] Greedy(double[] V, double money){
//返回结果的数组
int [] result = new int[V.length];
//先对数据进行挑选，先将零钱中面值大于要找的零钱进行剔除
int j=0;
//将挑选的数值进行贪婪最优化
for (int i=0; i<V.length;++i){
//向下取整
if (money>=V[i]){
int number=(int)Math.floor((money*100)/(V[i]*100));
if(money-number*V[i]==0){
result[j]=number;
++j;
break;
}else{
//出现数据泄露，最后money=0.00999999999988
money=money-number*V[i];
result[j]=number;
++j;
}
}else{
result[j]=0;
++j;
}
}
//进行结果反向验证
double sum=0;
for(int i=0; i<V.length;i++){
sum=sum+result[i]*V[i];
}
if (sum!=money){
result[result.length-1]+=1;
}
return result;
}
}
发表于 2019-09-07 21:07:04
回复(1)
def change(coins, n): len1 = len(coins) if len1 == 0 and n < 1 or n > 100000: return None ways = [0] * (n + 1) # 初始化 ways[0] = 1 for i in range(len1): for j in range(coins[i], n + 1): # 保证n小于等于100000，为了防止溢出，请将答案Mod 1000000007 ways[j] = (ways[j] + ways[j - coins[i]]) % 1000000007 print(ways[n]) if __name__ == '__main__': coins, n = [1, 2, 5, 10], int(input()) change(coins, n) |
发表于 2019-09-05 16:08:58
回复(0)
问题信息
通过挑战的用户
-
2022-11-26 16:28:28 -
2022-11-22 15:34:54 -
2022-11-16 16:05:26 -
2022-11-12 11:34:09 -
2022-11-04 15:24:01
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
