动态规划

设dp[i]为目标为i时需要的最少货币数，则dp的转移方程为dp[j] = min(dp[j], dp[j-arr[i]]+1)。

意思就是说比较当前目标值需要的货币数与当前目标值减去一个货币之后所需货币数加一（因为要达到这个目标值还需要加上这个被减去的货币）。

显然目标值为0时，需要的货币数为0，又因为是在dp里找最小值，所以从dp[1]一直到dp尾元素都需要初始化为一个很大的数。

代码如下：

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