---
# System prepended metadata

title: 0322. Coin Change
tags: [Leetcode, Dynamic Programming, Medium]

---

# 0322. Coin Change
###### tags: `Leetcode` `Medium` `Dynamic Programming`
Link: https://leetcode.com/problems/coin-change/
## 思路
基本的动态转移方程很明确
```dp[n] = min(dp[n-k1],dp[n-k2], ..., dp[n-ki]) +1```
其中```ki```表示```coins```数组中提供的面额.
## Code
```java=
class Solution {
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        int[] dp = new int[amount+1];
        for(int i=1; i<=amount; i++){
            dp[i] = Integer.MAX_VALUE/2;
            for(int j=0; j<n; j++){
                if(i>=coins[j]){
                    dp[i] = Math.min(dp[i], dp[i-coins[j]]+1);
                }
            }
        }
        return (dp[amount]<Integer.MAX_VALUE/2)?dp[amount]:-1;
    }
}
```