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

Question

我正在尝试解决以下问题（来自 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，其中一个可以使用缓存的结果。

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

Answer 1

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

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

@lru_cache(maxsize=None)
def ...

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

Applying memoization to the coin changing problem

python

algorithm

memoization

dynamic-programming