LeetCode 的硬币兑换问题超过了时间限制

Question

我正在尝试解决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 无法实现此实现吗？

Answer 1

似乎这件作品：

  fewest[i] = 1 + min(
            (fewest[i - coin] for coin in
                [c for c in coins if i - c >= 0]),
            default=math.inf)

检查所有硬币，过滤适当的硬币。

但是您可以对硬币名义值进行排序，并且仅针对给定的 i 遍历足够小的名义值。