The following solution's running time is independent of `amount`

and depends only `coins`

:

```
def gcd(a,b):
if b > a:
return gcd(b,a)
elif b == 0:
return a
else:
return gcd(b, a%b)
lcm = lambda a,b : a*b//gcd(a,b)
class Solution:
def coinChange(self, coins, amount):
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
# Checking Trivial Cases
if amount == 0:
return 0
if len(coins) == 0:
return -1
# Find the LCM of the coin sizes
l = 1
for c in coins:
l = lcm(l,c)
# Reduce to a case where amount is less than LCM if needed
if amount > l:
redCount = self.coinChange( coins, amount % l )
if redCount == -1:
return -1
else:
return redCount + (amount // l)*(l//max(coins))
# Dynamic Programming Part
count = [0] * (amount + 1)
for n in range(1, amount + 1):
prev = [ count[n-c] for c in coins if c <= n and count[n-c] != -1 ]
if len(prev) == 0:
count[n] = -1
else:
count[n] = min(prev) + 1
return count[amount]
```

The "dynamic programming" part only needs a number of steps equal to the least common multiple of the coin sizes rather than a number of steps proportional to `amount`

. Thus running time and space is proportional to the least common multiple of the coin sizes. This allows for handling cases such as `coins=[1]`

and `amount=10**10`

.