有1分，2分，5分，10分四种硬币，每种硬币数量无限，给定n_瓜子二手车笔试题

无敌爽爽

import java.util.Scanner;

public class Solution {
    int count = 0;
    int[] arr;

    public int calculateWays(int n) {
        arr = new int[n + 1];
        return calculateWays1(n);
    }
    //记忆化搜索递归
    private int calculateWays1(int n) {
        if (n < 0) 
            throw new IllegalArgumentException("input wrong");
        if (n == 0) 
            return 0;
        if (n == 1)
            return 1;
        if (n == 2 || n == 3)
            return 2;
        if (n == 4 || n == 5 || n == 6 || n == 7 || n == 8 || n == 9)
            return n - 1;
        if (n == 10)
            return 11;
        if (arr[n] != 0)
            return arr[n];
        int res = 0;
        res = Math.max(Math.max(calculateWays1(n - 1) + 1, calculateWays1(n - 2) + 2), Math.max(calculateWays1(n - 5) + 4, calculateWays1(n - 10) + 11));
        arr[n] = res;
        return res;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入钱数：");
        int n = sc.nextInt();
        Solution s = new Solution();
        int sum = s.calculateWays(n);
        System.out.println(sum);
    }
}

接楼上动态规划法，这是对应的递归解法，思路就是不断递归的寻找比n小1，2，5，10分的组合数量加组成1，2，5，10分的组合数量的最大值，个人认为递归算法更容易理解，但会反复计算很多重复的子问题，所以引入了记忆化搜索减少了计算次数，总体来讲由于递归本身的开销会比动态规划大，但递归思想适应性更广，理解两种解法对解类似的题目会更有帮助。

编辑于 2019-08-23 14:25:56 回复(2)

wanly

public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		sc.close();

		int coins[] = { 1, 2, 5, 10 };

		count(coins, 0, n);
		System.out.println(numcount);
	}


	// 递归
	static int numcount = 0;

	public static void count(int coins[], int index, int aim) {

		if (aim == 0) {
			numcount++;
			return;
		}
		if (index == 4) {
			return;
		}

		for (int i = 0; i * coins[index] <= aim; i++) {
			count(coins, index + 1, aim - i * coins[index]);
		}

	}

编辑于 2019-09-12 16:37:52 回复(1)

求求你别逼逼了

n=int(input())
list=[]
for i in range(0,n+1):
    for j in range(0,n+1):
        for k in range(0,n+1):
            for l in range(0,n+1):
               if j*1+k*2+5*k+l*10==n:
                   list.append(j)
print(len(list))

发表于 2019-08-17 10:17:27 回复(4)

Tulan

public static int countWays(int[] coins,int n) {   
        
        int[] dp = new int[n+1];         
        dp[0] = 1;  
        for(int i = 0;i < coins.length;++i){  
            for(int j = coins[i];j <= n;++j){ 
                dp[j] += dp[j-coins[i]];   
            }  
        }  
        return dp[n];  
    }

动态规划的经典题，直接copy了一段代码。对于每个n，都可以分解开来，它的组合数=每个硬币（n-面值）的组合数之和。

发表于 2019-08-13 10:33:45 回复(5)

SeeYou2099

package aadatastructureandalgorithm.dp;

import java.util.Scanner;

/**
 * @description: 
 * @author: 
 * @time: 2019/8/14 20:59
 */
public class CombinateCoins {
    int[] tempMost = null;
    int count;

    public CombinateCoins(int n) {
        if (n <= 0) {
            throw new IllegalArgumentException("");
        }
        if (n > 10) {
            tempMost = new int[n + 1];
            count = n + 1;
        } else {
            tempMost = new int[11];
            count = 11;
        }
        tempMost[0] = 0;
        tempMost[1] = 1;
        tempMost[2] = 2;
        tempMost[3] = 2;
        tempMost[4] = 3;
        tempMost[5] = 4;
        tempMost[6] = 5;
        tempMost[7] = 6;
        tempMost[8] = 7;
        tempMost[9] = 8;
        tempMost[10] = 11;

    }

    //蛮力法
    void combinateCoinsByBtute() {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入钱数");
        int n = scanner.nextInt();
        int sum = 0;
        int count = 0;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= (n / 2); j++) {
                for (int k = 0; k <= (n / 5); k++) {
                    for (int l = 0; l <= (n / 10); l++) {
                        if ((i + j * 2 + k * 5 + l * 10) == n) {
                            sum++;
                        }
                    }
                }
            }
        }
        System.out.println(sum);
    }

    //动态规划
    int combinateCoinsByDp(int n) {
        CombinateCoins combinateCoins = new CombinateCoins(n);
        if (n <= 10) {
            return combinateCoins.tempMost[n];
        }

        for (int i = 11; i <= n; i++) {
            int most = 0;
            for (int j = 1; j <= i / 2; j++) {
                int tempCount = tempMost[j] + tempMost[i - j];
                if (most < tempCount) {
                    most = tempCount;
                }
                tempMost[i] = most;
            }
        }
        return tempMost[n];
    }

    public static void main(String[] args) {
        while (true) {
            Scanner scanner = new Scanner(System.in);
            System.out.println("请输入钱数");
            int n = scanner.nextInt();
            CombinateCoins combinateCoins = new CombinateCoins(n);
            System.out.println(combinateCoins.combinateCoinsByDp(n));
        }
    }
}

发表于 2019-08-14 21:32:36 回复(0)

Mr.X-Ray

public int solution(int n){

int[] coins = {1,2,5,10};

int[] dp = new int[n+1];

dp[0]=1;

for(int i=0;i<coins.length;i++){

for(int j=coins[i];j<=n;j++){

dp[j]+=dp[j-coins[i]];

}

return dp[n];

}

发表于 2019-09-03 09:33:55 回复(0)

牛客693836602号

现在99

发表于 2020-11-06 19:56:14 回复(0)

_小十三

所以，这个题在行测里是闹哪样

发表于 2020-07-28 00:43:54 回复(0)

牛客310873341号

13

发表于 2020-03-28 00:04:14 回复(0)

只是不想说

'''
思路：求出10的取值范围，在取出10的基础上，然后在剩下的部分求出5的取值范围，
    进而在取出5的基础上，对剩下部分求出2的取值范围，ok次数到位了
'''
while True:
    try:
        n = int(input())
        a10 = n//10
        count = 0
        se = set([])#验证此算***不会存在重复的情况。。。。通过获取最后集合的长度与count是一样的，没有重复
        for i in range(0,a10+1):
            for j in range(0,(n-i*10)//5+1):
                temp = n-i*10-j*5
                for k in range(0,temp//2+1):
                    t2 = n-i*10-j*5-k*2
                    #print('10:',i,'    5:',j,'    2:',k,'    1:',t2,'    和：',i*10+j*5+k*2+t2)
                    se.add(str(i)+','+str(j)+','+str(k)+','+str(t2))
                    count+=1
        print(count)
    except:
        break

发表于 2019-09-23 17:18:22 回复(0)

dretrtg

public:
    int timu(int target){
        this->target = target;
        dfs(0);
        return count;
    }
private:
    int count = 0;
    vector<int> v;
    int total = 0, target;
    int a[] = {1,2,5,10};
    int dfs(int index){
        if(total == target){
            count++;
        }
        if(total > target)    return;
        for(int i = index; i < 4; i++){
            total += a[i];
            v.push_back(a[i]);
            dfs(i);
            v.pop_back();
            total -= a[i];
        }
    }

发表于 2019-09-20 12:29:19 回复(0)

一如既往201804131446533

import java.util.Scanner;

/**
 * @author wufuqiang
 * @title: study11
 * @projectName:wufuqiang_thread
 * @description: T0D0
 * @created 2019-09-18 09:02
 */
public class Main {

    // 计算 只含 5，2，1
    public static long count5(long m){
        long c = 0;
        for (long i = m/5;i > 0;i--){
            c = c + (m - 5*i)/2;
            c = c + 1;
        }
        return c;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long n = in.nextInt();
        long num = 0;
        // 只有 1
        long a = 1;
        // 只有1，2 必有2
        long b = n/2;
        // 只有1，2，5 必有5
        long c = 0;
        for (long i = n/5;i > 0;i--){
            c = c + (n - 5*i)/2;
            c = c + 1;
        }
        // 只有1，2，5，10 必有10
        long d = 0;
        for (long i = n/10;i > 0;i--){
            // 判断能否含有5
            if(n < 15){
                d = a + (n-10)/2;
                break;
            }else {
                d = d + count5((n - 10*i)); //含521
                d = d + (n - 10*i)/2;   //含21
                d = d + 1;  //含1
            }
        }
        num = (a + b + c + d)%1000000007;

        System.out.println(num);
    }
}

发表于 2019-09-18 14:26:27 回复(0)

鹿踏雾而来

import java.util.Scanner; public class Null { public static void main(String[]args){
        Scanner scanner = new Scanner(System.in);  int n = scanner.nextInt();  int[] dp = new int[n+1];  dp[0] = 1;  int[] coins = new int[]{1, 2, 5, 10};  for(int i = 0; i <coins.length; i++ ){ for(int j = coins[i]; j <= n; j++){
                dp[j] +=dp[j-coins[i]];  }
        }
        System.out.println(dp[n]);   }
}

发表于 2019-09-17 21:44:31 回复(0)

Ponder_xu

n=int(input())
a=[0,1,2,5,10]
dp=[[0 for j in range(5)] for i in range(n+1)]
for i in range(0,n+1):
    dp[i][1]=1  ###只用1硬币地话永远只有一种可能
for j in range(5):
    dp[0][j]=1
for i in range(1,n+1):
    for j in range(2,5):
        if i >=a[j]:
            dp[i][j]=dp[i-a[j]][j]+dp[i][j-1]
        else:
            dp[i][j]=dp[i][j-1]
print(dp[n][4])

在瓜子车的环境中，没有百分百通，当N=10000时，我代码输出的结果为1671170501，期望输出为671170494。于是我和上面贴出来的方法(网上大多可以查到的另外一种动态转移方法)做了对比，在n=1000,n=10000时结果是一样的，而且上图中这种时间更快，时间复杂度只有O(4n)。此外还和暴力法(当n=100，n=200)做了对比，输出的结果没有错误。

剩下的只有交给别的大佬解决了，如果有了解决方案请告知下我。

编辑于 2019-09-16 15:10:54 回复(1)

bxing

#include<iostream>

using namespace std;

int main(){
    int n;
    cin>>n;
    long long count=0;
    for(int i=0;i<=n/10;i++){
        for(int j=0;j<=(n-i*10)/5;j++){
            if(count+(n-i*10-j*5)/2+1>=(1e9+7))
                count=count+(n-i*10-j*5)/2+1-(1e9+7);
            else
                count+=(n-i*10-j*5)/2+1;

        }
    }
    cout<<count;

    return 0;
}

发表于 2019-09-03 16:37:31 回复(2)

你瞅啥瞅

import java.util.Scanner; public class qian2{ public static void main(String[] args){ Scanner in = new Scanner(System.in); int n = in.nextInt(); int []a = new int [4]; a[0]=10; a[1]=5; a[2]=2; a[3]=1; int t=0; for(int i=0;i<3;i++){ t =t+n/a[i]; } int ex=0; int num=1; for(int j=0;j<3;j++){ ex =n/a[j]; if(ex==0){ num =num*1; }else{ num=num*ex; } n = n % a[j]; if(n==0){ break; } } System.out.println(t+num); } }

发表于 2019-08-27 14:49:18 回复(0)

地下铁的心脏

pyhton代码：

def get_small_money_combination(n, coins):
    if min(coins) <= 0:
        raise ValueError("Coins with value %d not existing in this world")
    if n == 0:
        return 0
    old_comb = [1] * (n + 1)
    new_comb = [0] * (n + 1)
    for i in coins[1:]:
        for j in range(n + 1):
            for k in range(j // i + 1):
                new_comb[j] += old_comb[j - k * i]
        old_comb, new_comb = new_comb, [0] * (n + 1)
    return old_comb[-1]

状态转移方程为：

dp[i][m] = sum(dp[i-1][m-k*Vm] for k in range(0, m/Vm))

其中 dp[i][m] 代表有前 i 种硬币组成数字 m 的组合数，Vm 是第 i 种硬币的面值，参见https://blog.csdn.net/wickedvalley/article/details/76279480

发表于 2019-08-23 12:17:48 回复(0)

笑不出来_M

public void out(int n) {
    for (int i = 0; i <= n ; i++) {
        for (int j = 0; j <= n/2 ; j++) {
            for (int k = 0; k <= n/5; k++) {
                for (int m = 0; m <= n/10 ; m++) {
                    if (i + 2 * j + 5 * k + 10 * m == n) {
                        System.out.println("1分： " + i + " 2分：" + j + " 5分" + k + " 10分：" + m)
                    }
                }
            }
        }
    }
}

发表于 2019-08-19 16:45:56 回复(1)

Cardiac-

for(0--n){ ----1分钱

for(0--n/2){ -----2分钱

for(0--n/5){ -----5分钱

for(0 -- n/10){ ----10分钱

满足条件 ++；

}

发表于 2019-08-10 17:19:23 回复(1)

123456、、

 */ int n=789;//输入值  int type=0;  int sum=0;  for (int i = 0; i < n; i++) { sum+=1;  for (int j = 0; j <(n-i); j++) { sum+=2;  for (int k = 0; k <(n-i-j); k++) { sum+=5;  for (int l = 0; l <(n-i-j-k); l++) { sum+=10;  if(sum==n){ type++;  System.out.println("第"+type+"种：?"+i+"?"+j+"?"+k+"?"+l);  }
             }
         }
     }
 }

发表于 2019-08-09 17:10:03 回复(0)

有1分，2分，5分，10分四种硬币，每种硬币数量无限，给定n

问题信息

热门推荐

相关试题