题解 | 兑换零钱(一)

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 最少货币数
 * @param arr int整型一维数组 the array
 * @param arrLen int arr数组长度
 * @param aim int整型 the target
 * @return int整型
 */
 
#include <math.h>
#define min(x,y)    (x>y?y:x)
int minMoney(int* arr, int arrLen, int aim ) {
    // write code here

    //这个题目当时是做过的，我有点忘记它的这个条件了核心就是把那个
    //能找到就可以
    /*有思路了
        dp[i] = mount,
        这个下标就是aim,mount就是所需要的数量
        所以先搞一个数组
    */
  int *dp = malloc(sizeof(int)*(aim+1));
  dp[0] = 0;//初始值
  for(int i = 1;i<= aim;i++)
  {
    dp[i] = 999999;//先初始化为无穷大
    for(int j = 0;j<arrLen;j++)
    {
        if(i >= arr[j] &&dp[i-arr[j]] !=INFINITY)
        {
            dp[i] = min(dp[i],dp[i-arr[j]]+1);
        }
    }
  }
   return dp[aim]==999999?-1:dp[aim];
}

这个题目，当时实习面试时就考了这个，当时没有做出来，还是自己基础太过于薄弱了。