<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>

// e.g:- 1,1,1,2 and 2,1,1,1 are same {that's why we don't use for loop}

//Approach-1 (Recursion + Mempozation) : O(n*amount)
class Solution {
public:
    int n;
    int t[301][5001];
    

    // int solve(int i, vector<int>& coins, int amount) {
        
    //     if(amount == 0)
    //         return t[i][amount] = 1;
        
    //     if(i == n || amount < 0)
    //         return 0;
        
    //      if(t[i][amount] != -1)
    //         return t[i][amount];
        
    //     if(coins[i] > amount)
    //         return t[i][amount] = solve(i+1, coins, amount);
        
    //     int take = solve(i, coins, amount-coins[i]);
    //     int skip = solve(i+1, coins, amount);
        
    //     return t[i][amount] = take+skip;
        
    // }
    

   int solveTab(vector<int>& coins, int amt) {
        int n = coins.size();
        vector<vector<int>> dp(n + 1, vector<int>(amt + 1, 0));
        
        // There's exactly one way to make amount 0 (by not using any coins)
        for(int i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }
        
        // Fill the DP table
        for(int i = 1; i <= n; i++) {
            for(int amount = 1; amount <= amt; amount++) {
                int take = 0;
                if(amount >= coins[i - 1])  // Use i-1 because dp is 1-based indexing
                    take = dp[i][amount - coins[i - 1]];
                int skip = dp[i - 1][amount];
                
                dp[i][amount] = take + skip;
            }
        }
        
        return dp[n][amt];  // Return the number of ways to make amount using all coins
    }
    int change(int amount, vector<int>& coins) {
        n = coins.size();
        // memset(t, -1, sizeof(t));
        // return solve(0, coins, amount);

        return solveTab(coins,amount);

    }
};
26225