/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 最少货币数 * @param arr int整型一维数组 the array * @param arrLen int arr数组长度 * @param aim int整型 the target * @return int整型 */ #define min(a,b) a<b?a:b int minMoney(int* arr, int arrLen, int aim ) { // write code here if(arrLen == 0) return -1; int* dp = (int*)malloc(sizeof(int) * (aim + 1)); dp[0] = 0; for(int i = 1; i < aim + 1; i++) { dp[i] = aim + 1; for(int j = 0; j < arrLen; j++) { if(i - arr[j] >= 0) { // printf("发现货币%d小于当前目标%d\n", arr[j],i); dp[i] = min(dp[i - arr[j]] + 1, dp[i]); // printf("目前兑换%d花费最少的零钱张数是%d\n",i,dp[i]); } } } if(dp[aim] > aim) return -1; return dp[aim]; }