我正在嘗試解決LeetCode 上的Coin Change 問題:我想出了我認為與解決方案中提到的自下而上的動態編程方法相同的方法:import mathclass Solution: def coinChange(self, coins, amount): fewest = [0] * (amount + 1) for i in range(1, amount + 1): fewest[i] = 1 + min( (fewest[i - coin] for coin in [c for c in coins if i - c >= 0]), default=math.inf) return fewest[amount] if fewest[amount] < math.inf else -1以下是pytest我用來驗證解決方案的一些測試用例:def test_1(): assert Solution().coinChange([1, 2, 5], 1) == 1def test_2(): assert Solution().coinChange([1, 2, 5], 2) == 1def test_3(): assert Solution().coinChange([1, 2, 5], 3) == 2def test_4(): assert Solution().coinChange([1, 2, 5], 4) == 2def test_5(): assert Solution().coinChange([1, 2, 5], 5) == 1def test_67(): assert Solution().coinChange([1, 2, 5], 6) == 2 assert Solution().coinChange([1, 2, 5], 7) == 2def test_8(): assert Solution().coinChange([1, 2, 5], 8) == 3def test_11(): assert Solution().coinChange([1, 2, 5], 11) == 3def test_no_way(): assert Solution().coinChange([2], 3) == -1問題是我收到“超出時間限制”錯誤:但是,如果我復制這個測試用例并在本地運行它,我發現該算法只需要0.02s:import pytestdef test_time_limit_exceeded(): Solution().coinChange( [205, 37, 253, 463, 441, 129, 156, 429, 101, 423, 311], 6653)if __name__ == "__main__": pytest.main([__file__, '--duration', '1'])導致以下輸出:============================= test session starts ==============================platform darwin -- Python 3.6.6, pytest-3.8.1, py-1.6.0, pluggy-0.7.1rootdir: /Users/kurtpeek/GoogleDrive/CodeRust, inifile:collected 11 itemscoin_changing_leetcode2.py ........... [100%]=========================== slowest 1 test durations ===========================0.02s call coin_changing_leetcode2.py::test_time_limit_exceeded========================== 11 passed in 0.07 seconds ===========================知道為什么 LeetCode 無法實現此實現嗎?
2 回答

PIPIONE
TA貢獻1829條經驗 獲得超9個贊
似乎這件作品:
fewest[i] = 1 + min( (fewest[i - coin] for coin in [c for c in coins if i - c >= 0]), default=math.inf)
檢查所有硬幣,過濾適當的硬幣。
但是您可以對硬幣名義值進行排序,并且僅針對給定的 i 遍歷足夠小的名義值。
添加回答
舉報
0/150
提交
取消