<p>You are given an integer array <code>coins</code> representing coins of different denominations and an integer <code>amount</code> representing a total amount of money.</p>

<p>Return <em>the fewest number of coins that you need to make up that amount</em>. If that amount of money cannot be made up by any combination of the coins, return <code>-1</code>.</p>

<p>You may assume that you have an infinite number of each kind of coin.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> coins = [1,2,5], amount = 11
<strong>Output:</strong> 3
<strong>Explanation:</strong> 11 = 5 + 5 + 1
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> coins = [2], amount = 3
<strong>Output:</strong> -1
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> coins = [1], amount = 0
<strong>Output:</strong> 0
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= coins.length &lt;= 12</code></li>
	<li><code>1 &lt;= coins[i] &lt;= 2<sup>31</sup> - 1</code></li>
	<li><code>0 &lt;= amount &lt;= 10<sup>4</sup></code></li>
</ul>

class Solution {
public:
    int s(int i, int amt, vector<int>&coins,vector<vector<int>> &dp){
        if(amt<0) return 1e9;
        if(amt==0) return 0;
        if(i>=coins.size()) return 1e9;
        if(dp[i][amt]!=-1) return dp[i][amt];
       
        int take = 1e9;
        int notTake = s(i+1, amt, coins,dp);
        
        if(amt>=coins[i]){
            take = 1+s(i, amt-coins[i], coins,dp);
        }
        
        return dp[i][amt] =  min(take, notTake);
    }

    int coinChange(vector<int>& coins, int amount) {
        vector<vector<int>> dp(coins.size()+2, vector<int>(amount+1, -1));
        sort(coins.begin(),coins.end(), greater<int>());
        return s(0,amount, coins,dp)==1e9 ? -1:s(0,amount, coins,dp);
    }

    // int coinChange(vector<int>& coins, int amount) {
    //     vector<vector<int>> dp(coins.size()+1, vector<int>(amount+1, 0));
    //     for(int i=0;i<=coins.size();i++){
    //         for(int j=0;j<=amount;j++){
    //             if(j==0) dp[i][j]=0;
    //             int take = 1e9;
    //             int notTake = 1e9;
    //             if(i>0) notTake = dp[i-1][j];
    //             if(j>=coins[i]){
    //                 take = 1+ dp[i][j-coins[i]];
    //             }
    //             return dp[i][j] = min(take,notTake);
    //         }
    //     }

    //     return dp[coins.size()][amount]>=1e9 ? -1:dp[coins.size()][amount];
    // }

};


// class Solution {
// // private:
// //     int f(int index, int amount, vector<int>& coins){
// //         if(index==0){
// //             if(amount%coins[0]==0){
// //                 return amount/coins[0];
// //             }
// //             else return 1e9;
// //         }
// //         int notTake = 0+f(index-1,amount,coins);
// //         int take = 1e9;
// //         if(coins[index]<=amount){
// //             take = 1+f(index, amount-coins[index],coins);
// //         }     

// //         return min(take,notTake);
// //     }
// // public:
// //     int coinChange(vector<int>& coins, int amount) {
// //         int ans = f(coins.size()-1,amount,coins);
// //         if (ans>=1e9) return -1;
// //         else return ans;
// //     }

// // private:
// //     int f(int index, int amount, vector<int>& coins,vector<vector<int>> &dp){
// //         if(index==0){
// //             if(amount%coins[0]==0){
// //                 return amount/coins[0];
// //             }
// //             else return 1e9;
// //         }
// //         if (dp[index][amount]!=-1) return dp[index][amount];
// //         int notTake = 0+f(index-1,amount,coins,dp);
// //         int take = 1e9;
// //         if(coins[index]<=amount){
// //             take = 1+f(index, amount-coins[index],coins,dp);
// //         }     

// //         return dp[index][amount] = min(take,notTake);
// //     }
// public:
//     int coinChange(vector<int>& coins, int amount) {
//         int n = coins.size(); 
//         vector<vector<int>> dp(n,vector<int>(amount+1,-1));
//         for (int t = 0;t<=amount;t++){
//             if(t%coins[0]==0) dp[0][t] = t/coins[0];
//             else dp[0][t] = 1e9;
//         }
//         for(int i = 1;i<n;i++){
//             for(int t = 0;t<=amount;t++){
//                 int notTake = 0+dp[i-1][t];
//                 int take = 1e9;
//                 if(coins[i]<=t){
//                     take = 1+dp[i][t-coins[i]];
//                 }     
//                 dp[i][t] = min(take,notTake);
//             }
//         }
//         int ans = dp[n-1][amount];
//         if (ans>=1e9) return -1;
//         else return ans;

//     }
// };
56421