The easiest way to come up with an approach is to see the search graph or the search tree.
D&C
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
min_change = self.search_num_coins(coins, amount)
if min_change is not None:
return min_change
return -1
def search_num_coins(self, coins: List[int], amount: int) -> Optional[int]:
# base case
if amount < 0:
return None
if amount == 0:
return 0
min_change = None
# divide
for c in coins:
num_change = self.search_num_coins(coins, amount - c)
# merge
if num_change is not None:
if min_change is None:
min_change = 1 + num_change
else:
min_change = min(min_change, 1 + num_change)
return min_change
this algo is exponential and the exponent is the depth
if the recursion depth is too high, then this approach is not functional.
for example [2,3,6,7], 77 can cause a TLE on the OJ
Memoized Search
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
memo: Dict[int, Optional[int]] = {}
min_change = self.search_num_coins(coins, amount, memo)
if min_change is not None:
return min_change
return -1
def search_num_coins(
self, coins: List[int], amount: int, memo: Dict[int, Optional[int]]
) -> Optional[int]:
# base case
if amount < 0:
return None
if amount in memo:
return memo[amount]
if amount == 0:
return 0
min_change = Nonepy
# divide
for c in coins:
num_change = self.search_num_coins(coins, amount - c, memo)
# merge
if num_change is not None:
if min_change is None:
min_change = 1 + num_change
else:
min_change = min(min_change, 1 + num_change)
memo[amount] = min_change
return min_change
time is bounded pseudo polynomial
Greedy Boost
significantly reduce the search depth
for example [1,2,4], 32000
DP
# define by value
# dp[a] = the minimum number of coins to sum to amount a
# recursive step
# dp[a] = min(1 + dp[a-c] for all c in coins)
# base case
# dp[0] = 0
# topo order
# for a from 0 to amount
# final answer
# dp[amount]
def coinChange(self, coins: List[int], amount: int) -> int:
dp: Dict[int, int] = {}
# init
dp[0] = 0
# topo order
for a in range(amount):
if a not in dp:
continue
for c in coins:
if a + c > amount:
continue
if a + c in dp:
dp[a + c] = min(dp[a + c], 1 + dp[a])
else:
dp[a + c] = 1 + dp[a]
if amount in dp:
return dp[amount]
return -1
