1

我被要求使用动态编程来解决问题。我对动态编程的构成有不同的看法。我相信它需要一种“自下而上”的方法，首先解决最小的问题。

我有一个矛盾的信息，如果相同的子问题被多次解决，是否可以是动态编程，递归中经常出现这种情况。

例如。对于斐波那契，我可以有一个递归算法：

RecursiveFibonacci(n)
if (n=1 or n=2)
    return 1
else
    return RecursiveFibonacci(n-1) + RecursiveFibonacci(n-2)

在这种情况下，可能会一遍又一遍地解决相同的子问题。这是否呈现它不是动态编程？也就是说，如果我想要动态编程，我是否必须避免解决子问题，例如使用长度为 n 的数组并将解决方案存储到每个子问题（数组的第一个索引是 1、1、2、3、5、 8、13、21)?

Fibonacci(n)
F1 = 1
F2 = 1
for i=3 to n
    Fi=Fi-1 + Fi-2
return Fn
4

2 回答 2

3

动态程序通常可以用递归公式简洁地描述。

但是，如果您使用简单的递归计算机程序来实现它们，这些通常会因为您提出的原因而效率低下：重复相同的计算。斐波那契是重复计算的一个例子，尽管它不是一个动态程序。

有两种方法可以避免重复。

  1. 记忆。这里的想法是缓存为递归函数的每组参数计算的答案，并在缓存值存在时返回缓存值。

  2. 自下而上的表。在这里，您“展开”递归，以便将低于 i 的级别的结果组合到级别 i 的结果。这通常被描述为填写表格，其中级别是行。

任何 DP 算法都隐含其中一种方法。如果重复计算，则该算法不是 DP。所以你的问题的答案是“是的”。

举个例子……让我们尝试使用最少数量的硬币来找零 c 美分的问题，因为你有价值为 v_1、v_2、... v_n 的硬币。

令 N(c) 为制造 c 美分所需的最小硬币数。然后一个递归公式是

N(c) = 1 + min_{i = 1..n} N(c - v_i)

对于 k<0，基本情况是 N(0)=0 和 N(k)=inf。

要记住这一点，只需要一个映射 c 到 N(c) 的哈希表。

在这种情况下，“表”只有一个维度，很容易填写。假设我们有值 1、3、5 的硬币，那么 N 表以

  • N(0) = 0，初始条件。
  • N(1) = 1 + min(N(1-1), N(1-3), N(1-5) = 1 + min(0, inf, inf) = 1
  • N(2) = 1 + min(N(2-1), N(2-3), N(2-5) = 1 + min(1, inf, inf) = 2
  • N(3) = 1 + min(N(3-1), N(3-3), N(3-5) = 1 + min(2, 0, inf) = 1

你明白了。你总是可以用这种方式从 N(d), d < c 计算 N(c)。

在这种情况下，您只需要记住最后 5 个值，因为那是最大的硬币值。大多数 DP 都是相似的。只需要表格的几行即可获得下一个。

对于递归表达式中的 k 个自变量，该表是 k 维的。

于 2013-10-03T03:02:01.290 回答
0

我们会考虑一个问题的动态规划方法，如果它有

  1. 重叠子问题
  2. 最优子结构

用非常简单的话我们可以说动态规划有两个方面，它们是自顶向下和自底向上的方法。

在您的情况下，如果您正在谈论递归，这是一种自上而下的方法。在自上而下的方法中，我们将尝试编写递归解决方案或蛮力解决方案并记忆结果，以便在类似的子问题到来时尝试使用该结果，因此它是蛮力 + 记忆。我们可以通过简单的递归关系来实现这种蛮力方法。

于 2020-05-28T08:17:35.243 回答