C语言-动态规划-零钱兑换

1.问题描述

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

2.源码

#define _CRT_SECURE_NO_WARNINGS 
#include <stdio.h>
#include <stdlib.h>
int minCoins(int* coins, int n, int amount)
{
    int* dp = (int*)malloc((amount + 1) * sizeof(int)); // 动态分配dp数组
    dp[0] = 0; // 总金额为0时，需要的硬币个数为0
    for (int i = 1; i <= amount; i++)
    {
        dp[i] = amount + 1; // 初始化为一个不可能的值，用于比较取最小值
        for (int j = 0; j < n; j++)
        {
            if (coins[j] <= i)
            {
                dp[i] = dp[i] < dp[i - coins[j]] + 1 ? dp[i] : dp[i - coins[j]] + 1; // 状态转移方程
            }
        }
    }
    int result = dp[amount] > amount ? -1 : dp[amount]; // 如果dp[amount] > amount，则表示无法凑成总金额，返回-1
    free(dp); // 释放内存空间
    return result;
}
int main()
{
    int n; // 面额的数量
    printf("请输入硬币数量：");
    scanf("%d", &n);
    int* coins = (int*)malloc(n * sizeof(int)); // 动态分配硬币面额数组
    printf("请输入各个硬币的面额：");
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &coins[i]);
    }
    int amount; // 总金额
    printf("请输入总金额：");
    scanf("%d", &amount);
    int result = minCoins(coins, n, amount); // 调用函数求解最少硬币个数
    if (result == -1)
    {
        printf("无法凑成总金额\n"); // 如果无法凑成总金额，输出提示信息
    }
    else
    {
        printf("最少需要的硬币个数为：%d\n", result); // 输出结果
    }
    free(coins); // 释放内存空间
    return 0;
}

3.运行结果