DP problems

class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
if not coins:return -1
dp = [float('inf')]*(amount+1)
dp[0] = 0
coins= set(coins)
for i in range(1, amount+1):
for c in coins:
if i-c>=0:
dp[i] = min(dp[i], 1+dp[i-c])
return dp[-1] if dp[-1]!=float('inf') else -1

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jimmy Shen

Jimmy Shen

Data Scientist/MLE/SWE @takemobi