class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        if ( amount == 0 ) return 0;

        int m[amount+1];
        m[0]=0;
        for (int i = 1; i <=amount; ++i) {
            m[i]=INT_MAX;
            for (auto it:coins){
                if ( it<=i && m[i-it]!=INT_MAX){
                    m[i]=min(m[i],1+m[i-it]);

                }
            }
             
        }
        if (m[amount]==INT_MAX) return -1;
        return m[amount];
    }
};