LeetCode 518. 零钱兑换 II_系统运维

概述给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。示例 1: 输入: amount = 5, coins = [1, 2, 5]输出: 4解释: 有四种方式可以凑成总金额:5=55=2+2+15=2+1+1+15=1+1+1+1+1 示例 2: 输入: amount = 3, coins = [2]输出:

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

示例 1:

输入: amount = 5,coins = [1,2,5]输出: 4解释: 有四种方式可以凑成总金额:5=55=2+2+15=2+1+1+15=1+1+1+1+1

示例 2:

输入: amount = 3,coins = [2]输出: 0解释: 只用面额2的硬币不能凑成总金额3。

示例 3:

输入: amount = 10,coins = [10] 输出: 1

注意:

你可以假设：

0 <= amount (总金额) <= 5000 1 <= coin (硬币面额) <= 5000 硬币种类不超过 500 种结果符合 32 位符号整数

递归超时，动态规划没想到怎么做。

 1 public class Test { 2  3     static int cnt; 4     public static voID solve(int amount,int[] coins,int flag){ 5         int i,coinsSize = coins.length; 6         if(amount < 0){ 7             return; 8         } 9         if(amount == 0){10             cnt++;11             return;12         }13 14         for(i = 0; i < coinsSize; ++i){15             if(flag <= i){16                 flag = flag < i ? i : flag;17                 solve(amount-coins[i],coins,flag);18             }19         }20     }21     public static int change(int amount,int[] coins) {22         int flag = 0;23         cnt = 0;24         solve(amount,flag);25         return cnt;26     }27 28     public static voID main(String[] args) {29         int m[]={3,5,7,8,9,10,11};30         int am = 500;31         System.out.println(change(am,m));32     }33 }34 //35502874

C代码：

 1 #include <stdio.h> 2 #include <string.h> 3 int stack[100],top = 0; 4 voID solve(int amount,int* coins,int coinsSize,int& cnt,int flag){ 5     int i; 6     if(amount < 0){ 7         return; 8     } 9     if(amount == 0){10         for(i = 0; i < top; ++i)11             printf("%d ",stack[i]);12         printf("\n");13         for(i = 0; i < top; ++i)14             printf("%d ",coins[stack[i]]);15         printf("\n====================%d\n",flag);16         cnt++;17         return;18     }19 20     for(i = 0; i < coinsSize; ++i){21         if(flag <= i){22             flag = flag < i ? i : flag;23             stack[top++] = i;24             solve(amount-coins[i],coinsSize,cnt,flag);25             --top;26         }27     }28 }29 int change(int amount,int coinsSize) {30     int cnt = 0,flag = 0;31     solve(amount,flag);32     return cnt;33 }34 35 36 int main(){37     int m[]={1,2,5};38     int am = 5;39     printf("%d\n",change(am,m,3));40     return 0;41 }