首页 > 试题广场 >

换钱的方法数

[编程题]换钱的方法数

热度指数：7321 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定数组arr，设数组长度为n，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个整数aim，代表要找的钱数，求换钱的方法数有多少种。由于方法的种数比较大，所以要求输出对 $10^9+7$ 进行取模后的答案。

输入描述:

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

输出描述:

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

示例1

输入

4 15
5 10 25 1

输出

说明

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

备注:

时间复杂度,空间复杂度。

算法知识视频讲解

Java

码海泛舟

完全背包求方案数
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

动态规划，以示例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)