# Python O(amount) space, O(n*amount) time complexity

• ``````class Solution(object):
def coinChange(self, coins, amount):
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
if amount == 0:
return 0
dp = [amount+1]*(1+amount)
dp[0] = 0
for i in xrange(1,amount+1):
for j in xrange(len(coins)):
if coins[j]<=i:
dp[i] = min(dp[i],dp[i-coins[j]]+1)
return -1 if dp[-1] == amount+1 else dp[-1]
``````

Used the similar method, got TLE first.

OJ passed with 1728ms after using coin instead of coins[j]:

``````class Solution(object):
def coinChange(self, coins, amount):
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
if amount == 0:
return 0
dp = [amount+1]*(1+amount)
dp[0] = 0
for i in xrange(1,amount+1):
for coin in coins:
if coin<=i:
dp[i] = min(dp[i],dp[i-coin]+1)
return -1 if dp[-1] == amount+1 else dp[-1]``````

• I used similar method, 1820ms passed. So I guess the TLE bound should be around 2 seconds. not your fault

• here is my solution
it gets 1800+ms.
use "for coin in coins:" instead of "for j in xrange(len(coins)):"

``````class Solution(object):
def coinChange(self, coins, amount):
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
if not amount: return 0
INF = 0x7ffffffe
dp = [INF] * (amount + 1)
dp[0] = 0
for i in xrange(amount + 1):
for coin in coins:
if i + coin <= amount:
dp[i+coin] = min(dp[i+coin],dp[i] + 1)
return dp[amount] if dp[amount] != INF else -1
``````

• Thanks for sharing the trick . It worked for me :)

• thanks, it passed the oj when using coin instead of coins[j]

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.