首页 > 试题广场 >

换钱的方法数

[编程题]换钱的方法数
  • 热度指数：7414 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定数组arr，设数组长度为n，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个整数aim，代表要找的钱数，求换钱的方法数有多少种。由于方法的种数比较大，所以要求输出对进行取模后的答案。

输入描述:
输出包括两行，第一行包括两个整数n和aim。第二行包含n个整数，表示arr数组。


输出描述:
输出一个整数，表示换钱的方法数对取模后的答案。
示例1

输入

4 15
5 10 25 1

输出

6

说明

5*3=15

10*1+5*1=15

10*1+1*5=15

1*10+5*1=15

5*2+1*5=15

1*15=15
示例2

输入

5 1000
2 3 5 7 10

输出

20932712

备注:
时间复杂度,空间复杂度。
算法知识视频讲解
添加回答
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;

int main(){
    int n, m;
    cin>>n>>m;
    long a[n], dp[m+1];
    memset(dp, 0, sizeof(dp));
    for(int i=0;i<n;i++)
        cin>>a[i];
    dp[0] = 1;
    for(int i=0;i<n;i++)
        for(int j=a[i];j<=m;j++)
            dp[j] = (dp[j]+dp[j-a[i]])%MOD;
    cout<<dp[m]%MOD<<endl;
    return 0;
}

发表于 2020-02-13 01:56:21 回复(0)
无心2019头像 无心2019 
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,aim,M=1e9+7;
    cin>>n>>aim;
    if(n==0||aim<0)
    {
        cout<<-1<<endl;
        return 0;
    }
    vector<int>arr(n);
    for(int i=0;i<n;i++)
        cin>>arr[i];
    vector<int>dp(aim+1,0);
    dp[0]=1;                // 组成0元的个数
    for(int i=0;i<n;++i)
        for(int j=arr[i];j<=aim;++j)
            dp[j]=(dp[j]+dp[j-arr[i]])%M;
    cout<<dp[aim]<<endl;
    return 0;
}

发表于 2019-08-26 21:29:32 回复(0)
pein531头像 pein531
使用动态规划求解背包问题，记dp[i]为组成 i 的换钱方法数。动态规划的边界是dp[0]=1，表示只有当不选取任何硬币时，金额之和才为0。
对于面额为coin的硬币，当coin ≤ i ≤ target 时，如果存在一种硬币组合的金额之和等于 i−coin，则在该硬币组合中增加一个面额为 coin 的硬币，即可得到一种金额之和等于 i 的硬币组合。因此需要遍历coins，对于其中的每一种面额的硬币，更新数组 dp 中的每个大于或等于该面额的元素的值。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().trim().split(" ");
        int n = Integer.parseInt(params[0]);
        int target = Integer.parseInt(params[1]);
        final int MOD = 1000000007;
        String[] strArr = br.readLine().trim().split(" ");
        int[] coins = new int[n];
        for(int i = 0; i < n; i++) coins[i] = Integer.parseInt(strArr[i]);
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for(int coin: coins){
            for(int i = coin; i <= target; i++)
                dp[i] = (dp[i] + dp[i - coin]) % MOD;
        }
        System.out.println(dp[target]);
    }
}
如果动态规划的状态转移方程一开始很难想到，那我们可以通过记忆化搜索的递归版解法改编过来，只是将递归的调用，改成从DP表中取值就行：
1.记忆化搜索 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    static final int MOD = 1000000007;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().trim().split(" ");
        int n = Integer.parseInt(params[0]);
        int target = Integer.parseInt(params[1]);
        String[] strArr = br.readLine().trim().split(" ");
        int[] coins = new int[n];
        for(int i = 0; i < n; i++) coins[i] = Integer.parseInt(strArr[i]);
        int[][] memory = new int[n + 1][target + 1];
        // 从左边的硬币开始使用，往右尝试
        System.out.println(recurrent(coins, 0, target, memory));
    }
    
    private static int recurrent(int[] coins, int index, int rest, int[][] memory) {
        if(index == coins.length){
            return rest == 0? 1: 0;
        }else{
            // 缓存命中直接返回
            if(memory[index][rest] > 0) return memory[index][rest];
            // 否则递归计算
            memory[index][rest] = (recurrent(coins, index + 1, rest, memory) + (rest - coins[index] >= 0? recurrent(coins, index, rest - coins[index], memory): 0)) % MOD;
            return memory[index][rest];
        }
    }
}
2.二维DP 
import scala.io.StdIn

object Main {
    def main(args: Array[String]): Unit = {
        val in = StdIn
        var params = in.readLine().split(" ")
        val n = params(0).toInt
        val aim = params(1).toInt
        params = in.readLine().split(" ")
        val coins = Array.ofDim[Int](n)
        for(i <- coins.indices) coins(i) = params(i).toInt
        val dp = Array.ofDim[Long](n + 1, aim + 1)
        dp(n)(0) = 1
        for(index <- n - 1 to 0 by -1; rest <- 0 to aim){
            dp(index)(rest) = dp(index + 1)(rest)
            if(rest - coins(index) >= 0) dp(index)(rest) = (dp(index)(rest) + dp(index)(rest - coins(index))) % 1000000007
        }
        println(dp(0)(aim))
    }
}

编辑于 2021-11-21 11:13:58 回复(0)
麦芒2021头像 麦芒2021
完全背包问题，注意物品放在最前面 
#include "bits/stdc++.h"

using namespace std;
int main()
{
    const int M=1e9+7;
    int N;cin>>N;
    int aim;cin>>aim;
    vector<int> money(N);
    for(int i=0;i<N;i++)cin>>money[i];
    //sort(money.begin(),money.end());
    vector<int> dp(aim+1,0);
    //cout<<1;
    dp[0]=1;
    for(int j=0;j<N;j++)
    {
        for(int i=money[j];i<=aim;i++)
        {
            //if(i>money[j]){
            dp[i]=(dp[i]+dp[i-money[j]])%M;
            //else if(i==money[j])dp[i]++;
        }
        //cout<<dp[i]<<' ';
    }
    cout<<dp[aim];
    return 0;
}


发表于 2022-02-13 16:14:25 回复(0)
牛客79631828号头像 牛客79631828号 
import java.util.*;

public class Main {
    public static int mod = (int) 1e9+7;
    public static void main(String[] args) {
        Scanner sc = new Scanner (System.in);
        int n = sc.nextInt();
        int aim = sc.nextInt();
        int [] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        
        System.out.println(numDP(arr, aim));
    }
    
    public static int numDP (int[] arr, int aim) {
        if (arr == null || arr.length < 1 || aim < 0)
            return 0;
        int n = arr.length;
        long[][] dp = new long[n+1][aim+1];
        dp[n][0] = 1;
        for (int i = n-1; i >= 0; i--) {
            for (int j = 0; j<=aim; j++) {
                dp[i][j] = (dp[i+1][j]) % mod;
                if (j - arr[i] >= 0)
                    dp[i][j]+= (dp[i][j-arr[i]]) % mod;
                dp[i][j] = dp[i][j] % mod;
            }
        }
        return (int)dp[0][aim];
    }
}

发表于 2021-07-08 16:06:23 回复(0)
牛客887263087号头像 牛客887263087号 
#include <iostream>
#include <vector>
using namespace std;
const int mod = 1e9 + 7;

int process(int i, int rest, const vector<int>& v, vector<vector<int>>& dp){
    if(rest < 0)
        return 0;
    if(dp[i][rest] != -1)
        return dp[i][rest];
    if(rest == 0){
        dp[i][rest] = 1;
        return dp[i][rest];
    }
    //rest > 0
    if(i == v.size()){
        dp[i][rest] = 0;
        return dp[i][rest];
    }
    //rest > 0 ; i < v.size()
    long ans = 0;
    for(int num = 0; num * v[i] <= rest; num++){
        ans += (process(i + 1, rest - num * v[i], v, dp) % mod);
    }
    dp[i][rest] = ans % mod;
    return dp[i][rest];
}

int way(int aim, const vector<int>& v){
    vector<vector<int>> dp(v.size() + 1, vector<int>(aim + 1, -1));
    return process(0, aim, v, dp);
}

int main(void){
    int n, aim;
    cin >> n >> aim;
    vector<int> v(n);
    for(int i = 0; i < n; i++){
        cin >> v[i];
    }
    cout << way(aim, v) << endl;
    return 0;
}
傻瓜式办法就是记忆化搜索。
通过记忆化搜索，来进行笔试过程，最好用
遇到取模问题，需要注意使用%mod，和long的使用。 
#include <iostream>
#include <vector>
using namespace std;
const int mod = 1e9 + 7;

int way3(int aim, const vector<int>& v){
    int N = v.size();
    vector<vector<int>> dp(N + 1, vector<int>(aim + 1));
    for(int i = 0; i <= N; i++)
        dp[i][0] = 1;
    for(int i = N - 1; i >= 0; i--){
        for(int rest = 1; rest <= aim; rest++){
            dp[i][rest] = dp[i + 1][rest];
            if(rest - v[i] >= 0)
                dp[i][rest] = ((long)dp[i][rest] + (long)dp[i][rest - v[i]]) % mod;
        }
    }
    return dp[0][aim];
}

int main(void){
    int n, aim;
    cin >> n >> aim;
    vector<int> v(n);
    for(int i = 0; i < n; i++){
        cin >> v[i];
    }
    cout << way3(aim, v) << endl;
    return 0;
}
斜率优化的动态规划版本

编辑于 2021-06-02 18:10:53 回复(0)
路西迪西头像 路西迪西 
#include <cstdio>
#define mod 1000000007;
long long n, aim, arr[1010], dp[20010] = {1}, i, j;
int main(){
    scanf("%lld %lld", &n, &aim);
    for(i = 0; i < n; i++) scanf("%lld", &arr[i]);
    for(j = n-1; j >= 0; j--)
        for(i = arr[j]; i <= aim; i++)
            dp[i] = (dp[i] + dp[i - arr[j]]) % mod;
    printf("%lld", dp[aim]);
}
发表于 2021-02-05 16:10:08 回复(0)
cydqc头像 cydqc 
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int aim = sc.nextInt();
        int[] arr = new int[n+1];
        for(int i=1;i<=n;i++){
            arr[i]=sc.nextInt();
        }
        long[] dp = new long[aim+1];
        dp[0]=1;

        for(int i=1;i<=n;i++){
            for(int j=arr[i];j<=aim;j++){
                dp[j] = (dp[j]+dp[j-arr[i]])%1000000007;
            }
        }
        System.out.println(dp[aim]);
    }
}


发表于 2021-01-20 11:18:33 回复(0)
Java
momonn头像 momonn

完全背包求方案数
dp[j]:考虑前 n 种货币，组成面值 j 的方案数

import java.util.Scanner;

public class Main {
    static int N = 20010;
    static int mod = (int) (1e9 + 7);
    static int n, aim;
    static int[] dp = new int[N];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        aim = sc.nextInt();
        dp[0] = 1;
        for (int i = 0; i < n; i++) {
            int v = sc.nextInt();
            for (int j = v; j <= aim; j++) {
                dp[j] = (dp[j] + dp[j - v]) % mod;
            }
        }
        System.out.println(dp[aim]);
    }
}
发表于 2020-07-05 11:46:05 回复(0)
Java
jahentao头像 jahentao
动态规划，以示例1输入为例



时间复杂度O(N*aim)，空间复杂度压缩至O(aim)。
import java.util.*;

public class Main {

    public static final int mod = 1_000_000_007;

    public static int process(int[] arr, int n, int aim) {
        if (arr == null || arr.length == 0) return 0;
        int[] dp = new int[aim + 1];
        for (int i = 0; i < n; i++) {
            dp[0] = 1;
            for (int target = 0; target <= aim; target++) {
                if (target - arr[i] >= 0) {
                    if (i == 0)
                        dp[target] = dp[target - arr[i]];
                    else
                        dp[target] = (dp[target] + dp[target - arr[i]]) % mod;
                }
            }
        }
        return dp[aim];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int aim = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        System.out.println(process(arr, n, aim));
    }
}
发表于 2020-05-14 11:06:36 回复(0)
雄云枫头像 雄云枫 
#include<iostream>
(720)#include<vector>
using namespace std;

int change(int amount, vector<int> &coins) {
  int mod = 1e9 + 7;  
    
  if (amount == 0) return 1;
  if (coins.size() == 0)  return 0;
  vector<int> dp(amount + 1, 0);
  dp[0] = 1;   
  for (int i = 0; i < coins.size(); i++) {
    for (int j = coins[i]; j <= amount; j++) {
     dp[j] += dp[j - coins[i]]; 
     dp[j] %= mod;   
    }  
  }
  return dp[amount];  
}

int main () {
    int n, aim;
    cin >> n >> aim;
    int *arr = new int[n];
    vector<int> tmp;
    for (int i = 0; i < n; i++) {
      cin >> arr[i];
      tmp.push_back(arr[i]);  
    }
    cout << change(aim, tmp) << endl;
    return 0;
}
clear code to easy understand

发表于 2020-03-02 18:52:03 回复(1)
_Edison头像 _Edison 
//完全背包问题变种，二维数组会内存超限，所以用滚动数组实现1维的dp
#include<cstdio>
#include<iostream>
#include<cstdlib>
using namespace std;

int main(){
    int n,aim;
    cin>>n>>aim;
    long long arr[n];
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }

    long long dp[30000];
    dp[0] = 1;

    for(int i=0;i<n;i++){
        for(int j=1;j<=aim;j++){
            if(j>=arr[i])
                dp[j] = (dp[j-arr[i]]+dp[j])%1000000007;
        }
    }

    cout<<dp[aim]%1000000007;
    return 0;
}

发表于 2019-12-09 22:46:32 回复(1)
Python
天山剑客头像 天山剑客 
# -*- coding: utf-8 -*-
# !/usr/bin/python3

import sys

while True:
    s = sys.stdin.readline().strip()
    if s == '':
        break
    else:
        n, t = s.split()
        n = int(n)
        t = int(t)

        arr = list(map(int, input().split()))
        arr = sorted(arr)

        res = [0 for i in range(t + 1)]
        res[0] = 1

        for i in arr:
            if i > t:
                break
            for j in range(i, t + 1):
                res[j] = res[j] + res[j - i]

        # 输出一个整数，表示换钱的方法数对10 ^ 9 +7取模后的答案。
        print(res[t] % (pow(10, 9) + 7))
        
'''
解题思路：
动态规划核心状态转移方程式
f（n） = f(n - arr[0]) + f(n - arr[1]) + f(n - arr[2]) + ... + f(n - arr[i]) i为arr的长度
对于组成n的情况，每个arr[i]元与f（n - arr[i]）都可以组成一个n，所以把每种f（n - arr[i]）的种类数
相加，就找出了arr能组成n的种类。递归计算会重复计算f（n - arr[i]），运用斐波那契数列类似的方法，
从0开始遍历，重复利用计算过的f（n - arr[i]）。结果数值会过大，题目要求输出对10 ^ 9 +7取模后的答案。
'''

发表于 2019-11-14 19:15:07 回复(0)
弗洛伊德彪头像 弗洛伊德彪 
// dp
#include <bits/stdc++.h>
using namespace std;

int main()
{
    // 输出并创建数组
    int n,aim;
    cin>>n>>aim;
    vector<int>arr(n,0);
    for(int i=0;i<n;++i){
        cin>>arr[i];
    }
    int M=1e9+7;            // 定义模数
    vector<int>dp(aim+1,0); 
    dp[0]=1;                // 组成0元的个数
    for(int i=0;i<n;++i){
        for(int j=arr[i];j<=aim;++j){
            dp[j]=(dp[j]+dp[j-arr[i]])%M;
        }
    }
    cout<<dp[aim]<<endl;
    return 0;
}
结合换钱的最小货币数
主要是 动态转移方程的写法，主要是组成都进行累加
发表于 2019-08-21 14:31:20 回复(0)
我是一个有感情的菠萝头头像 我是一个有感情的菠萝头 
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int aim = sc.nextInt();
        int[] nums = new int[n];
        for(int i=0;i<n;i++){
            nums[i] = sc.nextInt();
        }
        //一维dp
        int[] dp = new int[aim+1];
        dp[0] = 1;
        for(int i=0;i<n;i++){
            for(int j=nums[i];j<=aim;j++){
                dp[j] = (dp[j] + dp[j-nums[i]]) % 1000000007;
            }
        }
        System.out.println(dp[aim]);
        /**
        二维dp
        int[][] dp = new int[n+1][aim+1];
        dp[0][0] = 1;
        for(int i=1;i<=n;i++){
            dp[i][0] = 1;
            for(int j=1;j<=aim;j++){
                //每个金额的货币，有取和不取两种选择。
                dp[i][j] = (dp[i-1][j] + (j>=nums[i-1]?dp[i][j-nums[i-1]]:0)) % 1000000007;
            }
        }
        System.out.println(dp[n][aim]);
        */
    }
}

发表于 2019-08-11 19:56:42 回复(0)
Python
雷凌云头像 雷凌云 
def count_way(arr, n):
    # 第0位是辅助位，代表面额数刚好等于金钱数的一种情况
    dp = [1] + [0]*n               # 不用任意面额的组合数
    for num in arr:
        for j in range(num, n+1):
            dp[j] += dp[j-num]
    return dp[-1]%(1000000007)
_,n = list(map(int, input().split(' ')))
arr = list(map(int, input().split(' ')))
print(count_way(arr, n))
同样是动态规划，python比其他语言慢了好多
编辑于 2019-08-10 14:11:29 回复(0)
提交观点

问题信息

动态规划
上传者：小小
难度：
16条回答 5681浏览

热门推荐

通过挑战的用户

查看代码

相关试题

换钱的方法数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号