DP version got TLE in couple of problems including Perfect Squares, Coin Change etc.
Normally Python runs a bit slower than C/C++ and should have relatively loose time limit threshold.
@1337c0d3r Thank you.
import math
class Solution(object):
_dp = [0]
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
# dp[i] is the least # of perfect square numbers which sum to i
dp = self._dp
for i in range(1, n + 1):
dp.append(float('inf'))
for i in range(n + 1):
for sqn in range(1, int(math.sqrt(i)) + 1):
dp[i] = min(dp[i], dp[i - sqn ** 2] + 1)
return dp[n]
class Solution(object):
def coinChange(self, coins, amount):
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
dp = [float('inf') for i in range(amount + 1)]
dp[0] = 0
for coin in coins:
for i in range(coin, amount + 1):
dp[i] = min(dp[i], dp[i - coin] + 1)
return -1 if dp[amount] == float('inf') else dp[amount]