Превышен лимит времени по проблеме смены монет LeetCode

Question

Я пытаюсь решить проблему Смена монеты на LeetCode :

Я пришел к тому, во что верюбыть таким же подходом динамического программирования снизу вверх, как упомянуто в решении:

import math


class 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) == 1


def test_2():
    assert Solution().coinChange([1, 2, 5], 2) == 1


def test_3():
    assert Solution().coinChange([1, 2, 5], 3) == 2


def test_4():
    assert Solution().coinChange([1, 2, 5], 4) == 2


def test_5():
    assert Solution().coinChange([1, 2, 5], 5) == 1


def test_67():
    assert Solution().coinChange([1, 2, 5], 6) == 2
    assert Solution().coinChange([1, 2, 5], 7) == 2


def test_8():
    assert Solution().coinChange([1, 2, 5], 8) == 3


def test_11():
    assert Solution().coinChange([1, 2, 5], 11) == 3


def test_no_way():
    assert Solution().coinChange([2], 3) == -1

Проблема заключается в том, что я получаю сообщение об ошибке «Превышено ограничение по времени»:

Однако, если я скопирую этот тестовый пример и запустлю его локально, я найдучто алгоритм занимает всего 0,02 с:

import pytest

def 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.1
rootdir: /Users/kurtpeek/GoogleDrive/CodeRust, inifile:
collected 11 items

coin_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

Я понял, что понимание списка [c for c in coins if i - c >= 0] оценивается len(coins) раз для каждого i, тогда как его нужно оценивать только один раз для каждого i.Это слегка переработанное решение было принято:

import math


class Solution:
    def coinChange(self, coins, amount):
        fewest = [0] * (amount + 1)
        for i in range(1, amount + 1):
            eligible_coins = [c for c in coins if i - c >= 0]
            fewest[i] = 1 + min(
                (fewest[i - coin] for coin in eligible_coins),
                default=math.inf)
        return fewest[amount] if fewest[amount] < math.inf else -1

Это все еще один из 10% лучших решений Python 3 для этой проблемы, хотя:

Answer 2

Кажется, что этот кусок:

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

проверяет все монеты, отфильтровывая соответствующие.

Но вы можете сортировать номиналы монет и проходить только по достаточно маленьким номиналам для данного i.