<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 coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        vector<long> prev(amount+1, 1e9), curr(amount+1, 1e9);  // Initialize DP table with large values
        prev[0]=0;  curr[0]=0;

        for (int i = 1; i <= amount; i++) {
            if (i % coins[0] == 0) {
                prev[i] = i / coins[0];  // Minimum coins required using only the first coin type
            }
        }

        // Fill the DP table for the remaining coins
        for (int ind = 1; ind < n; ind++) {
            for (int target = 1; target <= amount; target++) {
                long notTaken = prev[target];  // Not taking the current coin

                long taken = 1e9;  // Default to large value
                if (coins[ind] <= target)   taken = 1 + curr[target - coins[ind]];  // Taking the current coin

                curr[target] = min(notTaken, taken);  // Minimum of taking and not taking the coin
            }
            prev = curr;
            curr.resize(amount+1, 1e9);
        }

        // If the ans is still 1e9, it means it's not possible to form the amount
        long ans = prev[amount];
        return (ans >= 1e9) ? -1 : ans;
    }
};
27394