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

'''
You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

- inputs are small ints
- coins are unique
- coins are positive
    - take a coin amount goes down

Return the number of combinations that make up that amount.
- counting / combinatorics
- math, recurrence relations
- 1 2 2 vs 2 2 1
- avoid duplicates
    - same elements
        - keep track of counts
    - different order
        - stick to any ordering
        - allowed to sort

If that amount of money cannot be made up by any combination of the coins, return 0.
- divisibility and gcd

You may assume that you have an infinite number of each kind of coin.
- retake it
- when to stop? check to avoid goin negative

The answer is guaranteed to fit into a signed 32-bit integer.
- python

Using an array of ints count combinations that sum up to an amount

amount = amount, coins = coins

Decision

find the number of ways to make amount using coins

Starting with the ith coin what are actions

take the ith coin
    - have to make amount - coins[i], if coins[i] <= amount
skip the ith coin
    - go to the i + 1th coin

take i -> amount - coins, actions: take i, skip i...
skip i -> i + 1, actions: take i + 1, skip i + 1...

recursion

'''


class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        '''
        Bounds:
            i: [0, len(nums)], size = len(nums) + 1
            x: [0, amount], size = amount + 1

        Dependencies:

        Term (i, x) requires:

            take: (i, x - coins[i])
                - i does not change 
                - x requires x - coins[i]
                - x - coins before x
                - Small before Big
                - 0 ----> amount

            skip: (i + 1, x)
                - x does not change 
                - i requires i + 1
                - i + 1 before i
                - Big before small
                - len(coins) ----> 0

        '''
        dp_i1 = [0] * (amount + 1)
        dp_i1[0] = 1

        for i in range(len(coins) - 1, -1, -1):
            dp_i = [0] * (amount + 1)
            for x in range(0, amount + 1):
                dp_i[x] = dp_i1[x]
                if coins[i] <= x:
                    dp_i[x] += dp_i[x - coins[i]]
            dp_i1 = dp_i
        
        return dp_i1[amount]










17228