LeetCode 322. Coin Change

テーマ:You are given coins of different denominations and a total amount of money amount.Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1 .
Example 1: coins = [1, 2, 5] , amount = 11 return 3 (11 = 5 + 5 + 1)
Example 2: coins = [2] , amount = 3 return -1 .
Note: You may assume that you have an infinite number of each kind of coin.
問題解決の考え方:ダイナミックプランニングを使用してこの問題を解決します.重要なのは、サブ問題を定義することです.
コインcoins={A 1,A 2,...,An}があると仮定し,F(i)をamountがiの場合に必要な最小コイン数とすると,
F(i) = 1 + min{ F(i - coins[ j ]) } (j = 1,2,....,n);
(最初は問題を01バックに変換して解決しようと試みたが、coinsを減らしてソートし、01バックの問題で解決するという考え方だったが、最後は複雑でまだ正解していないので、その後はこの考えを諦めて上記の方法に転じた)

class Solution {
public:
    int coinChange(vector& coins, int amount) {
        int temp;
        vector coin_nums(amount+1,INT_MAX);
        coin_nums[0]=0;
        for(int i = 1 ; i <= amount; ++i){
            temp = INT_MAX;
            for(int j=0; j != coins.size();++j){
                if(i-coins[j]>=0){ ///  i      coins[j],       
                    temp = coin_nums[i-coins[j]]