class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int mx = amount + 1;
vector<int> dp(mx, 0x3f3f3f3f);
dp[0] = 0;
for(auto x : coins) {
for(int i = x; i <= amount; i++) {
dp[i] = min(dp[i - x] + 1, dp[i]);//状态转移式子
}
}
if(dp[amount] >= 0x3f3f3f3f) return -1;
else return dp[amount];
}
};