汇入DP解决方案-进行更改

Question

最近我读了一个练习DP的问题。我想不出一个，所以我尝试了一个递归解决方案，后来我修改了这个解决方案，使用了记忆化。问题陈述如下：-

做出改变。你会得到n种硬币面值v（1）

我从这里得到了问题

我的解决办法如下：

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中。当我从结束迭代到开始时，我有一个选择，要么选择一个面额，要么不选择它。如果我选择它，我然后递归以满足剩余的金额与较低的面额。如果我不选择它，我递归以满足较低面额的当前金额。

无论哪种方式，在给定的函数调用中，我都会找到满足给定数量的最佳（最低计数）。

从这里开始，我可以在沟通思想过程以达成DP解决方案方面得到一些帮助吗？我不是像任何HW那样做，这只是为了好玩和练习。我也不需要任何代码，只需要一些解释思考过程的帮助就可以了。

[编辑]

我记得读到过这样一篇文章：函数调用是昂贵的，这就是为什么自下而上（基于迭代）可能是首选的原因。这个问题有可能吗？

Answer 1

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

在这种情况下，您正在构建索引的值，成本基于：

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），因为它避免了函数调用和检查缓存中预先存在的值的开销。

Answer 2

在可能的情况下，这里有一种将记忆递归解决方案转换为“传统”自底向上DP解决方案的通用方法。

首先，让我们表达我们一般的“记忆化递归解”。这里，x表示在每次递归调用中更改的所有参数。我们希望这是一个正整数的元组——在你的情况下，是（index，成本）。我省略了递归中的任何常量（在您的情况下，L），并且我假设我有一个全局缓存。（但是FWIW，在Python中，你应该只使用标准库函数工具模块中的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的每个组件将使用连续递增的值，并将按顺序放置在缓存中，因此我们可以使用多维数组（嵌套lists，或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