题解 | #兑换零钱(一)#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 最少货币数
 * @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];
}