日出扶桑一丈高
人间万事细如毛
C++，动态规划。
比较经典的dp题，动态规划的一个最大的特点就是当前的最优解一定可以由之前的某个最优解得到，简而言之就是状态转移方程。
这道题也是一样的，因为零钱种类总是有限的，假设\(dp(x) \)表示\(x \)最少可以由(dp(x) \)枚硬币相加得到，我们可以写出如下的状态转移方程：
\[dp(x) = min\{dp(x-coins[0], x - coins[1], ..., x - coins[n-1])\} + 1\]显然，需要由小到大来得到\(dp(x) \)，所以就能写出代码了，需要注意的是\(dp(0) = 0 \)。
其他的值则默认为-1,。
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount + 1, -1);
dp[0] = 0;
for (const int &it : coins) {、
if (it <= amount) dp[it] = 1;
}
for (int i = 1; i <= amount; i++) {
for (const int &it : coins) {
int t = i - it;
if (t <= 0) continue;
if (dp[i] == -1 && dp[t] != -1)
dp[i] = dp[t] + 1;
else if (dp[t] != -1)
dp[i] = min(dp[t] + 1, dp[i]);
}
}
return dp[amount];
}
};
