将记忆化应用于硬币兑换问题

Applying memoization to the coin changing problem

我正在尝试解决以下问题(来自 CodeRust 3.0):

我想我会利用以下递归关系:在这个例子中,面额为(1, 2, 5)的7的方法数是0, 1, ..., 7的方法数之和] 面额 (2, 5)(即,每次选择第一个硬币的数量 1 时,对较小的面额集进行一次递归调用)。

为了应用记忆,我想我会使用 functools.lru_cache()。到目前为止,这是我的解决方案(包括 pytest 单元测试):

import pytest
import functools


@functools.lru_cache()
def solve_coin_change_dp(denominations, amount):
    if amount == 0:
        return 1
    if amount < 0:
        return 0
    if not denominations:
        return 0

    return sum(
        solve_coin_change_dp(
            denominations[1:],
            amount - i * denominations[0])
        for i in range(amount // denominations[0] + 1))


@pytest.fixture
def denominations():
    return (1, 2, 5)


def test_trivial():
    assert solve_coin_change_dp((1,), 1) == 1


def test_1(denominations):
    assert solve_coin_change_dp(denominations, 1) == 1


def test_2(denominations):
    assert solve_coin_change_dp(denominations, 2) == 2


def test_3(denominations):
    assert solve_coin_change_dp(denominations, 3) == 2


def test_4(denominations):
    assert solve_coin_change_dp(denominations, 4) == 3


def test_5(denominations):
    assert solve_coin_change_dp(denominations, 5) == 4


def test_7(denominations):
    assert solve_coin_change_dp(denominations, 7) == 6


def test_big_amount(denominations):
    solve_coin_change_dp(denominations, 1000)


if __name__ == "__main__":
    pytest.main([__file__, '--duration', '1'])

问题是 lru_cache 似乎根本没有帮助加快实施速度。对于 1000 的输入,程序仍然需要 ~10s 到 运行:

coin_changing.py ........                                                [100%]

=========================== slowest 1 test durations ===========================
10.31s call     coin_changing.py::test_big_amount
========================== 8 passed in 10.35 seconds ===========================

但是,如果我考虑函数调用,由于记忆化,我希望有 'saving'。例如,带有参数 (1, 2, 5), 5 的调用将导致 (2, 5), 5(2, 5), 4(2, 5), 3(2, 5), 2(2, 5), 1(2, 5), 0.其中第一个和第三个应该在某个时候依次导致 (5,), 3,其中一个可以使用缓存的结果。

简而言之,为什么这个记忆应用程序不起作用?

lru_cache 是一个 LRU 缓存。就像在缓存已满并且需要插入新元素时,它会驱逐最近最少使用的元素。默认缓存大小为 128。您的记忆化结果将被逐出。

设置 maxsize=None 以使用无限制的非 LRU 缓存:

@lru_cache(maxsize=None)
def ...