動機
複習dp
Problem
You are given an integer array coins
representing coins of different denominations and an integer amount
representing a total amount of money.
Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0
.
You may assume that you have an infinite number of each kind of coin.
The answer is guaranteed to fit into a signed 32-bit integer.
Example 1:
Input: amount = 5, coins = [1,2,5]Output: 4Explanation: there are four ways to make up the amount:5=55=2+2+15=2+1+1+15=1+1+1+1+1
Example 2:
Input: amount = 3, coins = [2]Output: 0Explanation: the amount of 3 cannot be made up just with coins of 2.
Example 3:
Input: amount = 10, coins = [10]Output: 1
Constraints:
1 <= coins.length <= 300
1 <= coins[i] <= 5000
- All the values of
coins
are unique. 0 <= amount <= 5000
Sol
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
@cache
def dp(acc,i):
if acc == amount:
return 1
elif acc > amount or i < 0:
return 0
else:
return sum([dp(acc+coins[i],i), dp(acc,i-1)])
return dp(0,len(coins)-1)