问题描述小明和小红在玩一个有趣的硬币游戏他们面前有 n 枚不同面值的硬币每枚硬币都可以无限次使用。现在他们想用这些硬币凑出总金额为 amount 的硬币组合但是希望使用的硬币数量最少。小明发现有些硬币组合方式使用的硬币数量较少而有些方式则较多。你能帮助小明设计一个算法找出使用硬币数量最少的组合方式吗要求设计一个动态规划算法找出凑成总金额所需的最少硬币个数。如果无法凑出总金额返回 -1。算法的时间复杂度应为 O(n * amount)其中 n 是硬币种类数amount 是目标金额。测试样例样例1输入coins [1, 2, 5],amount 11输出3解释11 5 5 1使用了 3 枚硬币这是最少的硬币数量组合。样例2输入coins [2],amount 3输出-1解释无法用面值 2 的硬币凑出总金额 3。样例3输入coins [1, 3, 4],amount 6输出2解释6 3 3使用了 2 枚硬币比 4113 枚更优。约束条件1 ≤ coins.length ≤ 121 ≤ coins[i] ≤ 2³¹ - 10 ≤ amount ≤ 10⁴硬币面值均为正整数注意硬币面值可能大于目标金额 amount这类硬币无法用于凑小金额在算法中应被跳过程序代码#include stdio.h#include stdlib.h#include limits.hint coinChange(int* coins, int coinsSize, int amount) {// dp[i] 表示凑出金额 i 的最少硬币数int* dp (int*)malloc((amount 1) * sizeof(int));// 初始化dp[0] 0;for (int i 1; i amount; i) {dp[i] INT_MAX;}// 动态规划for (int i 1; i amount; i) {for (int j 0; j coinsSize; j) {if (coins[j] i dp[i - coins[j]] ! INT_MAX) {if (dp[i - coins[j]] 1 dp[i]) {dp[i] dp[i - coins[j]] 1;}}}}int result (dp[amount] INT_MAX) ? -1 : dp[amount];free(dp);return result;}int main() {int coins1[] {1, 2, 5};printf(%d\n, coinChange(coins1, 3, 11)); // 3int coins2[] {2};printf(%d\n, coinChange(coins2, 1, 3)); // -1int coins3[] {1, 3, 4};printf(%d\n, coinChange(coins3, 3, 6)); // 2return 0;}#include stdio.h #include stdlib.h #include limits.h int coinChange(int* coins, int coinsSize, int amount) { // dp[i] 表示凑出金额 i 的最少硬币数 int* dp (int*)malloc((amount 1) * sizeof(int)); // 初始化 dp[0] 0; for (int i 1; i amount; i) { dp[i] INT_MAX; } // 动态规划 for (int i 1; i amount; i) { for (int j 0; j coinsSize; j) { if (coins[j] i dp[i - coins[j]] ! INT_MAX) { if (dp[i - coins[j]] 1 dp[i]) { dp[i] dp[i - coins[j]] 1; } } } } int result (dp[amount] INT_MAX) ? -1 : dp[amount]; free(dp); return result; } int main() { int coins1[] {1, 2, 5}; printf(%d\n, coinChange(coins1, 3, 11)); // 3 int coins2[] {2}; printf(%d\n, coinChange(coins2, 1, 3)); // -1 int coins3[] {1, 3, 4}; printf(%d\n, coinChange(coins3, 3, 6)); // 2 return 0; }运行结果