题目
一个正整数数组 arr ，表示不同面额的硬币；一个整数 n ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
每种硬币的数量是无限的。
思路
使用动态规划，动态规划的精髓是用小问题的解合并为大问题的解。这道题的大问题是什么？小问题是什么？
原问题是给定的金额换成零钱。小问题肯定是比给定金额小的金额。那是多少呢?
假如零钱种类为{1,2,5}，给定的金额为10，答案为f(10)。现在换了一个5元的。还剩5元需要换。有这个等式：
f(10)=f(5)+1。很显然，使用所有的面额换一次，剩下还没换的金额就是小问题，取所有小问题答案中的最小值+1,就是最终答案即
f(10) = min{f(10-5),f(10-1),f(10-2)} + 1
给定金额为n,零钱面额数组为arr
定义 f(n) 为最少的金币数量。则状态转移方程为：f(n) = min(f(n-arr[i]))+1, 0<=i<=arr.size()-1。
边界条件：f(0)=0，f(arr[i]) = 1,0<=i<=arr.size()-1
代码
#include <vector>
using namespace std;
class CoinChange {
public:
int coinChange(vector<int>& arr, int n) {
vector<int> dp(n+1,n+1);
//初始化
dp[0] = 0;
for(int i = 1;i <= n;i++) {
for(int j = 0;j < arr.size();j++) {
if (i >= arr[j]) {
dp[i] = min(dp[i],dp[i-arr[j]]+1);
}
}
}
return dp[n] > n ? -1 : dp[n];
}
};