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

using System;
using System.Collections.Generic;
using System.Linq;

class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 最少货币数
     * @param arr int整型一维数组 the array
     * @param aim int整型 the target
     * @return int整型
     */
    public Dictionary<int,int> dic = new Dictionary<int,int>();
    public int minMoney (List<int> arr, int aim) {
        if(aim == 0) return 0;
        if(aim < 0) return -1;
        if(dic.ContainsKey(aim)){
            return dic[aim];
        }
        else{
            int value = -2;
            List<int> nums = new List<int>();
            //Console.Write("aim:"+aim);
            for(int i = 0; i < arr.Count; i++){
                int curNum = minMoney(arr, aim - arr[i]);
                if(curNum >= 0) nums.Add(curNum);
            }
            if(nums.Count > 0) value = nums.Min();
            //Console.WriteLine("value:"+ value);
            dic.Add(aim, value + 1);
            return value + 1;
        }
    }
}