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

看到本题的标签是动态规划，就意味着最重要的是归纳出动态规划的关系式 设想一个dp数组，dp[1]表示组成1元需要的纸币，dp[10]表示组成10元需要的纸币，dp[100]表示组成100元需要的纸币 那么我们定义的时候vector dp(aim+1,max) 这里的max是最大方法，那么最大方法是多少呢，最不济的所有都是1元硬币，那么最多也就需要aim张，因此max>=aim+1 即可

• 首先，根据已给的硬币数组 初始化dp[arr[i]]=1
• 然后，遍历dp[money] 内部二次遍历硬币数组arr,关系表达式为 dp[i]=min(dp[i],dp[i-arr[j]]+1) dp[i]一开始可能是max 后来可能慢慢优化 从10 变为 8 再变为6等等 所以动态规划最重要的是获得关系式，以下是解析程序：

class Solution {
public:
    /**
     * 最少货币数
     * @param arr int整型vector the array
     * @param aim int整型 the target
     * @return int整型
     */
    int minMoney(vector<int>& arr, int aim) {
        if(aim==0)
            return 0;
        // write code here
        int max=aim+100;
        vector<int> dp(aim+1,max);
        int size=arr.size();
        
        //初始化已有的硬币
        for(int i=0;i<size;i++)
        {
            dp[arr[i]]=1;
        }
        for(int i=0;i<=aim;i++)
        {
            for(int j=0;j<size;j++)
            {
                if(i>=arr[j])
                    dp[i]=min(dp[i],dp[i-arr[j]]+1);
            }
        }
        return dp[aim]>=max?-1:dp[aim];
    }
};