322. Coin Change

解題思路

零錢問題之找最少零錢數。

程式碼

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int index[10001] = {0};
        for(int i=1; i<10001; i++)
            index[i] = amount + 1;
        for(int i=1; i<10001; i++)
        {
            for(int j=0; j<coins.size(); j++)
            {
                if((i - coins[j]) >= 0)
                {
                    index[i] = min(index[i], 1 + index[i - coins[j]]);
                }
            }
        }
        if(index[amount] == amount + 1) return -1;
        return index[amount];
    }
};