换钱的最少货币数

[编程题]换钱的最少货币数

热度指数：8764 时间限制：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

输出

说明

20=5*4

示例2

输入

3 0
5 2 3

输出

示例3

输入

2 2
3 5

输出

-1

备注:

时间复杂度，空间复杂度。

算法知识视频讲解

helloxuanbao

#include <stdio.h>

#define MIN(X,Y) ((X) < (Y) ? (X) : (Y))

int main(void) {
    int n, aim;
    scanf("%d %d", &n, &aim);
    if (n == 0) printf("%d\n", -1);
    int arr[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", arr + i);
    }
    int tmp;
    int dp[aim + 1];
    dp[0] = 0;
    for (int i = n - 1; i >= 0; i--) {
        for (int rest = 1; rest <= aim; rest++) {
            tmp = -1;
            if (rest - arr[i] >= 0 && dp[rest - arr[i]] != -1) {
                tmp = 1 + dp[rest - arr[i]];
            }
            if (i != n-1 && dp[rest] != -1) {
                tmp = tmp == -1 ? dp[rest] : MIN(tmp, dp[rest]);
            }
            dp[rest] = tmp;
        }
    }
    printf("%d\n", dp[aim]);
    return 0;
}

发表于 2022-01-28 15:32:12 回复(0)