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.
@hamster Could you please paste your code here which you think should be Accepted? I can extend the time limit so your code could be Accepted. Thanks.
@1337c0d3r Thank you.
- Perfect Squares
import math class Solution(object): _dp =  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]
- Coin Change (I got AC and TLE in a non consistent way.)
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 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]