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

Question

我正在尝试解决以下问题（来自CodeRust 3.0）：我想我会利用以下递归关系：在这个例子中，用面额制作 7(1, 2, 5)的方法数是0, 1, ..., 7用面额制作的方法数的总和(2, 5)（即，对较小的一组的递归调用第一枚硬币数量的每个选择的面额，1）。为了应用记忆，我想我会使用functools.lru_cache(). 到目前为止，这是我的解决方案（包括pytest单元测试）：import pytestimport [e-mail]_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.fixturedef denominations():    return (1, 2, 5)def test_trivial():    assert solve_coin_change_dp((1,), 1) == 1def test_1(denominations):    assert solve_coin_change_dp(denominations, 1) == 1def test_2(denominations):    assert solve_coin_change_dp(denominations, 2) == 2def test_3(denominations):    assert solve_coin_change_dp(denominations, 3) == 2def test_4(denominations):    assert solve_coin_change_dp(denominations, 4) == 3def test_5(denominations):    assert solve_coin_change_dp(denominations, 5) == 4def test_7(denominations):    assert solve_coin_change_dp(denominations, 7) == 6def test_big_amount(denominations):    solve_coin_change_dp(denominations, 1000)if __name__ == "__main__":    pytest.main([__file__, '--duration', '1'])