题目：零钱兑换
确定状态：dp[ i ]代表 为了凑出 i 元，所需要的硬币数量
状态转移：dp[ i ] = min(dp[ i ], dp[ i - coin ] + 1)，即金额 i 的最优解，必然是由某个较小的金额 i - coin 转移而来的。
1int coinChange(vector<int>& coins, int amount)
2{
3 std::vector<int> dp(amount + 1, amount + 1);
4 dp[0] = 0;
5
6 for(int i = 1; i <= amount; i++)
7 {
8 for(auto coin :coins)
9 {
10 if(coin <= i)
11 dp[i] = std::min(dp[i], dp[i - coin] + 1);
12 }
13 }
14 return dp[amount] > amount ? -1 : dp[amount];
15}