coin_change_ii
1# @leet start 2class Solution: 3 def change(self, amount: int, coins: list[int]) -> int: 4 """ 5 This question asks us to find the number of ways to make an amount 6 given an array of coins. 7 8 To do this, we want to create unique paths consisting of coins that 9 sum up to the total amount. Since each coin can be taken infinitely 10 many times, we want to dfs through the coins where we can either take 11 our current coin or choose to skip it. 12 13 So we can dfs where we always choose to take our current coin and 14 the next coin in order to find the ways we can get the answer. 15 16 At the end, there are three cases: 17 1. Curr == amount. Return 1 for the amount of ways to get here. 18 2. Curr > amount. Return 0, since this is invalid. 19 3. i > len(coins). We've used up all the coins. Return 0. 20 21 Finally, we need to build up our memoization table: 22 We need to create a two dimensional array that contains all the valid ways 23 we can reach our current location, and have a unique cache key, which 24 can be the current coin we're on + the amount we've gotten. 25 26 Finally, we set that value to either taking the current coin or skipping 27 and then return that value, so we can continue the recursion for all other 28 iterations. 29 """ 30 cache = {} 31 32 def dfs(i, curr): 33 if curr == amount: 34 return 1 35 if curr > amount: 36 return 0 37 if i == len(coins): 38 return 0 39 if (i, curr) in cache: 40 return cache[(i, curr)] 41 42 cache[(i, curr)] = dfs(i, curr + coins[i]) + dfs(i + 1, curr) 43 return cache[(i, curr)] 44 45 return dfs(0, 0) 46 47 48# @leet end 49 50 51def test(): 52 assert 2 + 2 == 4
class
Solution:
3class Solution: 4 def change(self, amount: int, coins: list[int]) -> int: 5 """ 6 This question asks us to find the number of ways to make an amount 7 given an array of coins. 8 9 To do this, we want to create unique paths consisting of coins that 10 sum up to the total amount. Since each coin can be taken infinitely 11 many times, we want to dfs through the coins where we can either take 12 our current coin or choose to skip it. 13 14 So we can dfs where we always choose to take our current coin and 15 the next coin in order to find the ways we can get the answer. 16 17 At the end, there are three cases: 18 1. Curr == amount. Return 1 for the amount of ways to get here. 19 2. Curr > amount. Return 0, since this is invalid. 20 3. i > len(coins). We've used up all the coins. Return 0. 21 22 Finally, we need to build up our memoization table: 23 We need to create a two dimensional array that contains all the valid ways 24 we can reach our current location, and have a unique cache key, which 25 can be the current coin we're on + the amount we've gotten. 26 27 Finally, we set that value to either taking the current coin or skipping 28 and then return that value, so we can continue the recursion for all other 29 iterations. 30 """ 31 cache = {} 32 33 def dfs(i, curr): 34 if curr == amount: 35 return 1 36 if curr > amount: 37 return 0 38 if i == len(coins): 39 return 0 40 if (i, curr) in cache: 41 return cache[(i, curr)] 42 43 cache[(i, curr)] = dfs(i, curr + coins[i]) + dfs(i + 1, curr) 44 return cache[(i, curr)] 45 46 return dfs(0, 0)
def
change(self, amount: int, coins: list[int]) -> int:
4 def change(self, amount: int, coins: list[int]) -> int: 5 """ 6 This question asks us to find the number of ways to make an amount 7 given an array of coins. 8 9 To do this, we want to create unique paths consisting of coins that 10 sum up to the total amount. Since each coin can be taken infinitely 11 many times, we want to dfs through the coins where we can either take 12 our current coin or choose to skip it. 13 14 So we can dfs where we always choose to take our current coin and 15 the next coin in order to find the ways we can get the answer. 16 17 At the end, there are three cases: 18 1. Curr == amount. Return 1 for the amount of ways to get here. 19 2. Curr > amount. Return 0, since this is invalid. 20 3. i > len(coins). We've used up all the coins. Return 0. 21 22 Finally, we need to build up our memoization table: 23 We need to create a two dimensional array that contains all the valid ways 24 we can reach our current location, and have a unique cache key, which 25 can be the current coin we're on + the amount we've gotten. 26 27 Finally, we set that value to either taking the current coin or skipping 28 and then return that value, so we can continue the recursion for all other 29 iterations. 30 """ 31 cache = {} 32 33 def dfs(i, curr): 34 if curr == amount: 35 return 1 36 if curr > amount: 37 return 0 38 if i == len(coins): 39 return 0 40 if (i, curr) in cache: 41 return cache[(i, curr)] 42 43 cache[(i, curr)] = dfs(i, curr + coins[i]) + dfs(i + 1, curr) 44 return cache[(i, curr)] 45 46 return dfs(0, 0)
This question asks us to find the number of ways to make an amount given an array of coins.
To do this, we want to create unique paths consisting of coins that sum up to the total amount. Since each coin can be taken infinitely many times, we want to dfs through the coins where we can either take our current coin or choose to skip it.
So we can dfs where we always choose to take our current coin and the next coin in order to find the ways we can get the answer.
At the end, there are three cases:
- Curr == amount. Return 1 for the amount of ways to get here.
- Curr > amount. Return 0, since this is invalid.
- i > len(coins). We've used up all the coins. Return 0.
Finally, we need to build up our memoization table: We need to create a two dimensional array that contains all the valid ways we can reach our current location, and have a unique cache key, which can be the current coin we're on + the amount we've gotten.
Finally, we set that value to either taking the current coin or skipping and then return that value, so we can continue the recursion for all other iterations.
def
test():