记忆化到动态规划解法 - 找零问题

1 投票

2 回答

693 浏览

数据工程师

提问于 2025-04-18 11:24

最近我在练习动态规划（DP）时遇到了一个问题。我一开始没能想到解决办法，所以尝试了一个递归的方法，后来又修改成了带备忘录的版本。问题的描述如下：

找零。你有n种面值的硬币，面值分别是 v(1) < v(2) < ... < v(n)（都是整数）。假设 v(1) = 1，这样你就可以为任何金额 C 找零。请给出一个算法，尽可能少地使用硬币来找零金额 C。

这个问题我是在这里找到的。

我的解决方案如下：

def memoized_make_change(L, index, cost, d):
    if index == 0:
        return cost

    if (index, cost) in d:
        return d[(index, cost)]

    count = cost / L[index]
    val1 = memoized_make_change(L, index-1, cost%L[index], d) + count
    val2 = memoized_make_change(L, index-1, cost, d)

    x = min(val1, val2)
    d[(index, cost)] = x
    return x

这是我对问题解决方案的理解。假设面值按升序存储在 L 中。当我从后往前遍历时，我可以选择使用某个面值的硬币，也可以选择不使用。如果我选择使用它，那么我就递归地去解决剩下的金额，使用更小面值的硬币。如果我不选择它，那么我就递归地去解决当前金额，使用更小面值的硬币。

无论哪种情况，在某个函数调用中，我都会找到满足给定金额的最佳方案（即使用的硬币数量最少）。

我能否得到一些帮助，帮助我从这里开始思考，最终达到动态规划的解决方案？我这样做不是为了完成作业，只是为了娱乐和练习。我其实也不需要代码，只需要一些关于思考过程的解释就很好。

[编辑]

我记得读过函数调用是比较耗费资源的，这也是为什么底层迭代（基于循环）可能更受欢迎的原因。这在这个问题上有可能吗？

递归算法设计最优解动态规划资源优化备忘录找零问题硬币组合

2 个回答

我建议你考虑一下你正在构建的值和你需要的值之间的关系。

在这个例子中，你正在为索引和成本构建一个值，基于：

index-1 and cost
index-1 and cost%L[index]

你要寻找的是一种遍历选择的方法，这样你就能确保所有需要的东西都已经提前计算好了。

在这种情况下，你可以简单地把代码改成迭代的方法：

for each choice of index 0 upwards:
    for each choice of cost:
        compute value corresponding to index,cost

实际上，我发现对于简单的问题，迭代的方法通常会快很多（比如快4倍），因为它避免了函数调用的开销和检查缓存中已有值的步骤。

回答于 2025-04-18 由 Python大师

分享举报

这里有一个将记忆化递归解决方案转换为“传统”自下而上的动态规划方法的通用思路，前提是这种转换是可能的。

首先，我们来表达一下我们的“记忆化递归解决方案”。在这里，x代表每次递归调用时变化的所有参数。我们希望这个参数是一个正整数的元组——在你的例子中，就是(index, cost)。我省略了在递归中保持不变的任何东西（在你的例子中是L），并假设我有一个全局的cache（缓存）。不过，顺便说一下，在Python中，你应该直接使用标准库functools模块中的lru_cache装饰器，而不是自己管理缓存。

To solve for(x):
    If x in cache: return cache[x]
    Handle base cases, i.e. where one or more components of x is zero
    Otherwise:
        Make one or more recursive calls
        Combine those results into `result`
        cache[x] = result 
        return result

动态规划的基本思想就是先计算基础情况，然后逐步向上推进：

To solve for(x):
    For y starting at (0, 0, ...) and increasing towards x:
        Do all the stuff from above

但是，当我们以这种方式安排代码时，会发生两个有趣的事情：

只要y值的顺序选择得当（当然，当只有一个向量分量时，这一点很简单），我们可以确保递归调用的结果总是在缓存中（也就是说，我们之前已经计算过这些结果，因为在循环的前一次迭代中y有那个值）。所以我们可以直接用查找缓存的方式来替代实际的递归调用。
由于y的每个分量都会使用连续增加的值，并且会按顺序放入缓存，我们可以使用多维数组（嵌套的list，或者Numpy数组）来存储这些值，而不是使用字典。

所以我们得到的结果大致是：

To solve for(x):
    cache = multidimensional array sized according to x
    for i in range(first component of x):
        for j in ...:
            (as many loops as needed; better yet use `itertools.product`)
            If this is a base case, write the appropriate value to cache
            Otherwise, compute "recursive" index values to use, look up
            the values, perform the computation and store the result
    return the appropriate ("last") value from cache

回答于 2025-04-18 由 Python大师

分享举报

记忆化到动态规划解法 - 找零问题

2 个回答

撰写回答