<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 number of combinations that make up that amount</em>. If that amount of money cannot be made up by any combination of the coins, return <code>0</code>.</p>

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

<p>The answer is <strong>guaranteed</strong> to fit into a signed <strong>32-bit</strong> integer.</p>

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

<pre>
<strong>Input:</strong> amount = 5, coins = [1,2,5]
<strong>Output:</strong> 4
<strong>Explanation:</strong> there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
</pre>

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

<pre>
<strong>Input:</strong> amount = 3, coins = [2]
<strong>Output:</strong> 0
<strong>Explanation:</strong> the amount of 3 cannot be made up just with coins of 2.
</pre>

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

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

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

<ul>
	<li><code>1 &lt;= coins.length &lt;= 300</code></li>
	<li><code>1 &lt;= coins[i] &lt;= 5000</code></li>
	<li>All the values of <code>coins</code> are <strong>unique</strong>.</li>
	<li><code>0 &lt;= amount &lt;= 5000</code></li>
</ul>


    class MyHash
{
public:
  size_t operator () (const pair<int, int>& tuple) const
  {
    return hash<int>()(tuple.first) ^ hash<int>()(tuple.second);
  }
};

class Solution {
    vector<vector<int>> tab;
    vector<int> tab_cc;

public:
 
    int changeCoins (vector<int>& coins, int n, int amount)
    {
        //assert (amount >= 0);
        
        if (amount == 0)
          return 1;

        if (n <= 0)
        {
            return 0;
        }

        if (tab[amount][n] != -1)
            return tab[amount][n];

        
        int changedCoins = changeCoins (coins, n-1, amount);
        
        if (amount >= coins[n-1]) 
            changedCoins += changeCoins (coins, n, amount - coins[n-1]);

        return tab[amount][n] = changedCoins;
    }


//   int changeCoins2_leetcode518_dp (vector<int>& coins, int amount)
//     {
//     int n = coins.size(), curr_amount , curr_n;
//         vector<vector<int>> dp(amount+1, vector <int>(n + 1, 0));
        
//         dp[0][0] = 1;
//         for (curr_n = 1; curr_n <= n; curr_n++)
//         {
//           for (curr_amount = 0; curr_amount <= amount; curr_amount++)
//           {
//             dp[curr_amount][curr_n] = dp[curr_amount][curr_n - 1];
//             if (curr_amount >= coins[curr_n - 1])
//             {
//               dp[curr_amount][curr_n] += dp[curr_amount - coins[curr_n-1]][curr_n];
//             }
//           }
//         }   

//         return dp[amount][n];
//     }

int changeCoins2_leetcode518_dp (vector<int>& coins, int amount)
    {
    int n = coins.size(), curr_amount , curr_n;
        vector<vector<int>> dp(amount+1, vector <int>(n + 1, 0));
        
        dp[0][0] = 1;
        for (curr_amount = 0; curr_amount <= amount; curr_amount++)
        {
          for (curr_n = 1; curr_n <= n; curr_n++) 
          {
            dp[curr_amount][curr_n] = dp[curr_amount][curr_n - 1];
            if (curr_amount >= coins[curr_n - 1])
            {
              dp[curr_amount][curr_n] += dp[curr_amount - coins[curr_n-1]][curr_n];
            }
          }
        }   

        return dp[amount][n];
    }

// int changeCoins2_leetcode518_dp2 (vector<int>& coins, int amount)
//     {
//     int n = coins.size(), curr_amount , curr_n;
//         vector<int> dp(amount+1);
        
//         dp[0][0] = 1;
//         for (curr_n = 1; curr_n <= n; curr_n++)
//         {
//           for (curr_amount = 0; curr_amount <= amount; curr_amount++)
//           {
//             if (curr_amount >= coins[curr_n - 1])
//             {
//               dp[curr_amount] += dp[curr_amount - coins[curr_n-1]];
//             }
//           }
//         }   

//         return dp[amount];
//     }

    int changeCoinsMap (vector<int>& coins, int n, int amount, unordered_map<pair<int, int>, int, MyHash>& cacheMap)
    {
        assert (amount >= 0);
        
        if (n == 0)
            {
                if (amount ==0 ) 
                    return 1;

                 return 0;
       
            }
            
        auto it =  cacheMap.find ({amount, n});
        if (it != cacheMap.end())
             return it->second;

        int changedCoins = 0, curr_amount = amount;
        int countLastCoin = amount / coins[n-1];
        for (int i = 0; i<=countLastCoin; i++)
        {
            changedCoins += changeCoinsMap (coins, n-1, curr_amount ,cacheMap);
            curr_amount -= coins[n-1];
        }

        return cacheMap[{amount, n}] = changedCoins;
    }


    // int changeCoins2 (vector<int>& coins, int amount)
    // {
    // int n = coins.size() ;
    //     vector<vector<int>> dp(n+1, vector <int>(amount + 1, 0));
        
    //     dp[0][0] = 1;
    //     for (int curr_n = 1; curr_n <=n ; curr_n++)
    //     {
    //         for (int curr_amount = 0; curr_amount <= amount; curr_amount++)
    //         {
    //             int changedCoins = 0, temp_amount = curr_amount;
    //             int countLastCoin = curr_amount / coins[curr_n-1];
    //             for (int i = 0; i<=countLastCoin; i++)
    //             {
    //                 changedCoins += dp[curr_n-1][temp_amount];
    //                 temp_amount -= coins[curr_n-1];
    //             }

    //             dp[curr_n][curr_amount] = changedCoins;
    //         }
    //     }

    //     return dp[n][amount];
    //     }


    // int changeCoins3 (vector<int>& coins, int amount)
    // {
    // int n = coins.size(), curr_amount ;
    //     vector<vector<int>> dp(2, vector <int>(amount + 1, 0));
        

    //     dp[0][0] = 1;
    //     int prev_n_dp_idx =0, n_dp_idx = 1;
    //     for (int curr_n = 1; curr_n <=n ; curr_n++)
    //     {
    //         for (curr_amount = 0; curr_amount <= amount; curr_amount++)
    //         {
    //             int changedCoins = 0, temp_amount = curr_amount;
    //             int countLastCoin = curr_amount / coins[curr_n-1];
    //             for (int i = 0; i<=countLastCoin; i++)
    //             {
    //                 changedCoins += dp[prev_n_dp_idx][temp_amount];
    //                 temp_amount -= coins[curr_n-1];
    //             }

    //             dp[n_dp_idx][curr_amount] = changedCoins;
    //         }

    //         prev_n_dp_idx = n_dp_idx;
    //         n_dp_idx = (n_dp_idx + 1) & 1; 
    //     }

    //     return dp[prev_n_dp_idx][amount];
    //     }

    // int changeCoins4 (vector<int>& coins, int amount)
    // {
    //     assert (amount >= 0);

    //     if (amount ==0 )
    //      return 1;
        
    //     if (tab_cc[amount] != -1)
    //         return tab_cc[amount];

    //     int changedCoins = 0;
    //     for (int i = 0; i<=coins.size(); i++)
    //     {
    //         if (amount < coins[i])
    //             continue;

    //         changedCoins += changeCoins4 (coins, amount - coins[i]);
    //     // }

    // //     return tab_cc[amount] = changedCoins;
    // // }



    int change(int amount, vector<int>& coins) {

        unordered_map<pair<int, int>, int, MyHash> cacheMap;
        return changeCoinsMap (coins, coins.size(),  amount, 
                                cacheMap);
    
        // tab_cc = vector<int> (amount+1, -1);
        // return changeCoins4 (coins, amount);
  
        // return changeCoins3(coins, amount);
        // if (amount < 0)
        //     return 0;

        //return  changeCoins2_leetcode518_dp (coins,amount);
         tab = vector<vector<int>> (amount+1, vector <int>(coins.size()+1, -1));
         return changeCoins (coins, coins.size(), amount);
    }
};
27095