algorithm - 什么是动态规划？

Question

什么是动态规划？

它与递归、记忆等有何不同？

我已经阅读了关于它的维基百科文章，但我仍然不太了解它。

Answer 1

动态编程是指您使用过去的知识来更轻松地解决未来的问题。

一个很好的例子是求解 n=1,000,002 的斐波那契数列。

这将是一个非常漫长的过程，但是如果我给你 n=1,000,000 和 n=1,000,001 的结果呢？突然间，这个问题变得更容易处理了。

动态规划在字符串问题中被大量使用，例如字符串编辑问题。您解决问题的子集，然后使用该信息解决更困难的原始问题。

使用动态编程，您通常将结果存储在某种表中。当您需要问题的答案时，您可以参考该表并查看您是否已经知道它是什么。如果没有，您可以使用表中的数据为自己提供一个通往答案的垫脚石。

Cormen Algorithms 这本书有一个关于动态规划的精彩章节。而且它在 Google 图书上是免费的！在这里查看。

Answer 2

动态编程是一种用于避免在递归算法中多次计算相同子问题的技术。

让我们以斐波那契数的简单示例为例：找到由下式定义的第 n^个斐波那契数

F _n = F _n-1 + F _n-2和 F ₀ = 0，F ₁ = 1

递归

显而易见的方法是递归：

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1

    return fibonacci(n - 1) + fibonacci(n - 2)

动态规划

• 自上而下 - 记忆

递归做了很多不必要的计算，因为给定的斐波那契数将被计算多次。一个简单的改进方法是缓存结果：

cache = {}

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n in cache:
        return cache[n]

    cache[n] = fibonacci(n - 1) + fibonacci(n - 2)

    return cache[n]

• 自下而上

一个更好的方法是通过以正确的顺序评估结果来完全摆脱递归：

cache = {}

def fibonacci(n):
    cache[0] = 0
    cache[1] = 1

    for i in range(2, n + 1):
        cache[i] = cache[i - 1] +  cache[i - 2]

    return cache[n]

我们甚至可以使用常量空间并在此过程中只存储必要的部分结果：

def fibonacci(n):
  fi_minus_2 = 0
  fi_minus_1 = 1

  for i in range(2, n + 1):
      fi = fi_minus_1 + fi_minus_2
      fi_minus_1, fi_minus_2 = fi, fi_minus_1

  return fi

• 如何应用动态规划？

  1. 找到问题中的递归。
  2. 自上而下：将每个子问题的答案存储在一个表中，以避免重新计算它们。
  3. 自下而上：找到正确的顺序来评估结果，以便在需要时可以获得部分结果。

动态编程通常适用于具有固有从左到右顺序的问题，例如字符串、树或整数序列。如果朴素的递归算法没有多次计算同一个子问题，动态规划将无济于事。

我做了一系列问题来帮助理解逻辑：https ://github.com/tristanguigue/dynamic-programing

Answer 3

记忆是存储函数调用的先前结果（给定相同的输入，真正的函数总是返回相同的东西）。在存储结果之前，它对算法复杂性没有影响。

递归是函数调用自身的方法，通常使用较小的数据集。由于大多数递归函数都可以转换为类似的迭代函数，因此这对算法复杂度也没有影响。

动态规划是解决更容易解决的子问题并从中建立答案的过程。大多数 DP 算法将处于贪婪算法（如果存在）和指数（枚举所有可能性并找到最好的）算法之间的运行时间。

• DP算法可以用递归来实现，但它们不是必须的。
• DP 算法不能通过记忆来加速，因为每个子问题只被解决（或调用的“解决”函数）一次。

Answer 4

这是对算法的优化，可以缩短运行时间。

虽然贪心算法通常被称为幼稚算法，因为它可能在同一组数据上运行多次，但动态编程通过更深入地了解必须存储以帮助构建最终解决方案的部分结果来避免这个陷阱。

一个简单的示例是仅通过对解决方案有贡献的节点遍历树或图，或者将您迄今为止找到的解决方案放入表中，这样您就可以避免一遍又一遍地遍历相同的节点。

这是一个适合动态规划的问题示例，来自 UVA 的在线评委：Edit Steps Ladder。

我将简要介绍一下这个问题分析的重要部分，取自《编程挑战》一书，我建议你看看。

好好看看这个问题，如果我们定义一个成本函数来告诉我们两个字符串之间的距离，我们有两个考虑三种自然类型的变化：

替换 - 将模式“s”中的单个字符更改为文本“t”中的不同字符，例如将“shot”更改为“spot”。

插入 - 将单个字符插入模式“s”以帮助它匹配文本“t”，例如将“ago”更改为“agog”。

删除 - 从模式“s”中删除单个字符以帮助它匹配文本“t”，例如将“小时”更改为“我们的”。

当我们将每个操作设置为花费一个步骤时，我们定义了两个字符串之间的编辑距离。那么我们如何计算呢？

我们可以通过观察字符串中的最后一个字符必须匹配、替换、插入或删除来定义递归算法。在最后一次编辑操作中删除字符会留下一对操作留下一对更小的字符串。令 i 和 j 分别是 和 t 的相关前缀的最后一个字符。最后一次操作后有三对较短的字符串，对应匹配/替换、插入或删除后的字符串。如果我们知道编辑三对较小字符串的成本，我们可以决定哪个选项会导致最佳解决方案并相应地选择该选项。我们可以通过递归这个很棒的东西来了解这个成本：

#define MATCH 0 /* enumerated type symbol for match */
#define INSERT 1 /* enumerated type symbol for insert */
#define DELETE 2 /* enumerated type symbol for delete */


int string_compare(char *s, char *t, int i, int j)

{

    int k; /* counter */
    int opt[3]; /* cost of the three options */
    int lowest_cost; /* lowest cost */
    if (i == 0) return(j * indel(’ ’));
    if (j == 0) return(i * indel(’ ’));
    opt[MATCH] = string_compare(s,t,i-1,j-1) +
      match(s[i],t[j]);
    opt[INSERT] = string_compare(s,t,i,j-1) +
      indel(t[j]);
    opt[DELETE] = string_compare(s,t,i-1,j) +
      indel(s[i]);
    lowest_cost = opt[MATCH];
    for (k=INSERT; k<=DELETE; k++)
    if (opt[k] < lowest_cost) lowest_cost = opt[k];
    return( lowest_cost );

}

这个算法是正确的，但也非常慢。

在我们的计算机上运行，​​比较两个 11 个字符的字符串需要几秒钟的时间，然后计算就消失在 never-never Land on any longer。

为什么算法这么慢？它需要指数级的时间，因为它一次又一次地重新计算值。在字符串中的每个位置，递归都以三种方式分支，这意味着它以至少 3^n 的速度增长——实际上，甚至更快，因为大多数调用只减少两个索引中的一个，而不是两个索引。

那么我们如何才能使算法实用呢？重要的观察是这些递归调用中的大多数都在计算之前已经计算过的东西。我们怎么知道？好吧，只能有|s| · |t| 可能的唯一递归调用，因为只有那么多不同的 (i, j) 对用作递归调用的参数。

通过将这些 (i, j) 对中的每一个的值存储在一个表中，我们可以避免重新计算它们，只需根据需要查找它们。

该表是一个二维矩阵 m，其中每个 |s|·|t| 单元格包含此子问题的最优解的成本，以及解释我们如何到达此位置的父指针：

typedef struct {
int cost; /* cost of reaching this cell */
int parent; /* parent cell */
} cell;

cell m[MAXLEN+1][MAXLEN+1]; /* dynamic programming table */

动态编程版本与递归版本有三个不同之处。

首先，它使用表查找而不是递归调用来获取中间值。

**其次，**它更新每个单元格的父字段，这将使我们能够在以后重建编辑序列。

**第三，**第三，它使用更通用的目标cell()函数进行检测，而不是仅返回 m[|s|][|t|].cost。这将使我们能够将此例程应用于更广泛的问题。

在这里，对收集最佳部分结果所需的非常特殊的分析是使解决方案成为“动态”解决方案的原因。

这是同一问题的替代完整解决方案。即使它的执行方式不同，它也是一个“动态”的。我建议您通过将其提交给 UVA 的在线评委来查看该解决方案的效率。我发现如何如此有效地解决如此繁重的问题令人惊讶。

Answer 5

动态规划的关键是“重叠子问题”和“最优子结构”。问题的这些性质意味着最优解是由其子问题的最优解组成的。例如，最短路径问题表现出最优子结构。从 A 到 C 的最短路径是从 A 到某个节点 B 的最短路径，然后是从该节点 B 到 C 的最短路径。

更详细地说，要解决最短路径问题，您将：

• 找到从起始节点到接触它的每个节点的距离（比如从 A 到 B 和 C）
• 找到从这些节点到接触它们的节点的距离（从 B 到 D 和 E，从 C 到 E 和 F）
• 我们现在知道了从 A 到 E 的最短路径：对于我们访问过的某个节点 x（B 或 C），它是 Ax 和 xE 的最短和
• 重复这个过程，直到我们到达最终的目标节点

因为我们是自下而上地工作，所以当需要使用子问题时，我们已经有了解决方案，方法是记忆它们。

请记住，动态规划问题必须同时具有重叠子问题和最优子结构。生成斐波那契数列不是动态规划问题；它利用记忆化，因为它有重叠的子问题，但它没有最优子结构（因为不涉及优化问题）。

Answer 6

动态规划

定义

动态规划 (DP) 是一种用于解决具有重叠子问题的问题的通用算法设计技术。这项技术是由美国数学家“理查德·贝尔曼”在 1950 年代发明的。

关键理念

关键思想是保存重叠的较小子问题的答案以避免重新计算。

动态规划属性

• 使用较小实例的解决方案解决实例。
• 可能需要多次使用较小实例的解决方案，因此将其结果存储在表中。
• 因此，每个较小的实例只求解一次。
• 额外的空间用于节省时间。

Answer 7

我对动态编程（针对特定类型问题的强大算法）也很陌生

用最简单的话来说，只需将动态编程视为一种使用先前知识的递归方法

以前的知识在这里最重要，跟踪您已经拥有的子问题的解决方案。

考虑这个，来自维基百科的 dp 最基本的例子

寻找斐波那契数列

function fib(n)   // naive implementation
    if n <=1 return n
    return fib(n − 1) + fib(n − 2)

让我们用 n = 5 来分解函数调用

fib(5)
fib(4) + fib(3)
(fib(3) + fib(2)) + (fib(2) + fib(1))
((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

特别是，fib(2) 从头开始​​计算了 3 次。在更大的例子中，更多的 fib 值或子问题被重新计算，导致指数时间算法。

现在，让我们通过将我们已经找到的值存储在数据结构中来尝试一下，比如Map

var m := map(0 → 0, 1 → 1)
function fib(n)
    if key n is not in map m 
        m[n] := fib(n − 1) + fib(n − 2)
    return m[n]

在这里，如果我们还没有，我们将在地图中保存子问题的解决方案。这种保存我们已经计算过的值的技术被称为记忆化。

最后，对于一个问题，首先尝试找到状态（可能的子问题并尝试考虑更好的递归方法，以便您可以将先前子问题的解决方案用于进一步的解决方案）。

Answer 8

动态规划是一种解决具有重叠子问题的问题的技术。动态规划算法只解决每个子问题一次，然后将其答案保存在表（数组）中。避免每次遇到子问题时重新计算答案的工作。动态规划的基本思想是：避免两次计算相同的东西，通常通过保留子问题的已知结果表。

开发动态规划算法的七个步骤如下：

1. 建立一个递归属性，为问题的一个实例提供解决方案。
2. 根据递归性质开发递归算法
3. 查看问题的相同实例是否在递归调用中再次得到解决
4. 开发记忆递归算法
5. 查看将数据存储在内存中的模式
6. 将记忆递归算法转换为迭代算法
7. 根据需要使用存储优化迭代算法（存储优化）

Answer 9

简而言之，递归记忆和动态编程之间的区别

顾名思义，动态规划就是使用之前的计算值来动态构造下一个新的解决方案

在哪里应用动态规划：如果您的解决方案基于最优子结构和重叠子问题，那么在这种情况下，使用较早的计算值将很有用，因此您不必重新计算它。这是自下而上的方法。假设您需要计算 fib(n) 在这种情况下您需要做的就是将先前计算的 fib(n-1) 和 fib(n-2) 的值相加

递归：基本上将您的问题细分为更小的部分以轻松解决它，但请记住，如果我们之前在其他递归调用中计算出相同的值，它不会避免重新计算。

记忆化：基本上将旧计算的递归值存储在表中称为记忆化，如果它已经通过以前的调用计算过，它将避免重新计算，因此任何值都将计算一次。所以在计算之前我们检查这个值是否已经计算过，如果已经计算过，那么我们从表中返回相同的值而不是重新计算。这也是自上而下的方法

Answer 10

Recursive这是斐波那契数列的, Top-down,Bottom-up方法的简单 Python 代码示例：

递归：O(2 ⁿ )

def fib_recursive(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fib_recursive(n-1) + fib_recursive(n-2)


print(fib_recursive(40))

自上而下：O(n) 对更大的输入有效

def fib_memoize_or_top_down(n, mem):
    if mem[n] is not 0:
        return mem[n]
    else:
        mem[n] = fib_memoize_or_top_down(n-1, mem) + fib_memoize_or_top_down(n-2, mem)
        return mem[n]


n = 40
mem = [0] * (n+1)
mem[1] = 1
mem[2] = 1
print(fib_memoize_or_top_down(n, mem))

自下而上：O(n) 为了简单和小输入大小

def fib_bottom_up(n):
    mem = [0] * (n+1)
    mem[1] = 1
    mem[2] = 1
    if n == 1 or n == 2:
        return 1

    for i in range(3, n+1):
        mem[i] = mem[i-1] + mem[i-2]

    return mem[n]


print(fib_bottom_up(40))