coin_change 

 1# @leet start
 2class Solution:
 3    def coinChange(self, coins: list[int], amount: int) -> int:
 4        """
 5        The coin change problem asks us to find the minimum number of coins
 6        required to make change for an amount.
 7
 8        The intuition is that to make the amount of 0, we need 0 coins,
 9        and where each amount = coin, we need 1 coin.
10
11        Next, we know that we can make any amount n where n - coin is already in
12        our dp array.
13
14        For example, with [2, 3]
15        To make 5, we can first take either a 2 or 3 and then another 2 or 3.
16        So, this should cost 2 coins.
17        If we wanted to make 10, we require 2 5s, or 4 coins.
18        Thus, to make progress, we can iterate through the coins and set our
19        current cost to 1 + dp[n - coin], and do this until we reach our amount.
20
21        We can then return dp[amount] to finish off the problem.
22        """
23        dp = [float("inf")] * (amount + 1)
24        dp[0] = 0
25
26        for coin in coins:
27            if len(dp) > coin:
28                dp[coin] = 1
29
30        for n in range(amount + 1):
31            for coin in coins:
32                if n - coin > 0:
33                    dp[n] = min(dp[n], 1 + dp[n - coin])
34
35        return -1 if dp[amount] == float("inf") else dp[amount]
36
37
38# @leet end
39
40
41def test():
42    assert 2 + 2 == 4
class Solution: 
 3class Solution:
 4    def coinChange(self, coins: list[int], amount: int) -> int:
 5        """
 6        The coin change problem asks us to find the minimum number of coins
 7        required to make change for an amount.
 8
 9        The intuition is that to make the amount of 0, we need 0 coins,
10        and where each amount = coin, we need 1 coin.
11
12        Next, we know that we can make any amount n where n - coin is already in
13        our dp array.
14
15        For example, with [2, 3]
16        To make 5, we can first take either a 2 or 3 and then another 2 or 3.
17        So, this should cost 2 coins.
18        If we wanted to make 10, we require 2 5s, or 4 coins.
19        Thus, to make progress, we can iterate through the coins and set our
20        current cost to 1 + dp[n - coin], and do this until we reach our amount.
21
22        We can then return dp[amount] to finish off the problem.
23        """
24        dp = [float("inf")] * (amount + 1)
25        dp[0] = 0
26
27        for coin in coins:
28            if len(dp) > coin:
29                dp[coin] = 1
30
31        for n in range(amount + 1):
32            for coin in coins:
33                if n - coin > 0:
34                    dp[n] = min(dp[n], 1 + dp[n - coin])
35
36        return -1 if dp[amount] == float("inf") else dp[amount]
def coinChange(self, coins: list[int], amount: int) -> int: 
 4    def coinChange(self, coins: list[int], amount: int) -> int:
 5        """
 6        The coin change problem asks us to find the minimum number of coins
 7        required to make change for an amount.
 8
 9        The intuition is that to make the amount of 0, we need 0 coins,
10        and where each amount = coin, we need 1 coin.
11
12        Next, we know that we can make any amount n where n - coin is already in
13        our dp array.
14
15        For example, with [2, 3]
16        To make 5, we can first take either a 2 or 3 and then another 2 or 3.
17        So, this should cost 2 coins.
18        If we wanted to make 10, we require 2 5s, or 4 coins.
19        Thus, to make progress, we can iterate through the coins and set our
20        current cost to 1 + dp[n - coin], and do this until we reach our amount.
21
22        We can then return dp[amount] to finish off the problem.
23        """
24        dp = [float("inf")] * (amount + 1)
25        dp[0] = 0
26
27        for coin in coins:
28            if len(dp) > coin:
29                dp[coin] = 1
30
31        for n in range(amount + 1):
32            for coin in coins:
33                if n - coin > 0:
34                    dp[n] = min(dp[n], 1 + dp[n - coin])
35
36        return -1 if dp[amount] == float("inf") else dp[amount]

The coin change problem asks us to find the minimum number of coins required to make change for an amount.

The intuition is that to make the amount of 0, we need 0 coins, and where each amount = coin, we need 1 coin.

Next, we know that we can make any amount n where n - coin is already in our dp array.

For example, with [2, 3] To make 5, we can first take either a 2 or 3 and then another 2 or 3. So, this should cost 2 coins. If we wanted to make 10, we require 2 5s, or 4 coins. Thus, to make progress, we can iterate through the coins and set our current cost to 1 + dp[n - coin], and do this until we reach our amount.

We can then return dp[amount] to finish off the problem.

def test(): 
42def test():
43    assert 2 + 2 == 4