首页 文章

什么是动态编程？

提问于
浏览 次
235

什么是 dynamic programming ？

它与递归，记忆等有什么不同？

我已经阅读了wikipedia article，但我仍然不太了解它 .

algorithm dynamic-programming

12 回答

  • 60

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

    一个很好的例子是解决n = 1,000,002的Fibonacci序列 .

    这将是一个非常漫长的过程，但如果我给你n = 1,000,000和n = 1,000,001的结果怎么办？突然间问题变得更加易于管理 .

    动态编程在字符串问题中经常使用，例如字符串编辑问题 . 您解决了问题的一个子集，然后使用该信息来解决更难的原始问题 .

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

    Cormen算法书有一个关于动态编程的伟大章节 . 它在Google图书上免费！看看here.

    回复于
  • 0

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

    我们来看一下斐波那契数的简单例子：找到由第i个定义的第n个斐波纳契数

    Fn = Fn-1 Fn-2且F0 = 0，F1 = 1

    递归

    显而易见的方法是递归：

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

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

    动态编程

    • Top Down - Memoization

    递归会进行大量不必要的计算，因为给定的斐波那契数将被计算多次 . 一种简单的方法是缓存结果：

    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]
    • Bottom-Up

    更好的方法是通过以正确的顺序评估结果来全面消除递归：

    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

    • How apply dynamic programming?

    • 找到问题中的递归 .

    • 自上而下：将每个子问题的答案存储在表中，以避免重新计算它们 .

    • 自下而上：找到正确的顺序来评估结果，以便在需要时提供部分结果 .

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

    我提出了一些问题来帮助理解逻辑：https://github.com/tristanguigue/dynamic-programing

    回复于
  • 33

    这是类似主题的my answe r

    从...开始

    如果你想测试自己，我对在线评委的选择是

    而且当然

    您还可以检查优秀的大学算法课程

    毕竟，如果你无法解决问题，那么请问这里有很多算法成瘾者

    回复于
  • 128

    Memoization是存储函数调用的先前结果的时候（实际函数总是返回相同的东西，给定相同的输入） . 在存储结果之前，它对算法复杂性没有影响 .

    递归是调用自身的函数的方法，通常使用较小的数据集 . 由于大多数递归函数可以转换为类似的迭代函数，因此这也不会对算法复杂性产生影响 .

    动态编程是解决更容易解决的子问题并从中解决问题的过程 . 大多数DP算法将处于贪婪算法（如果存在）和指数（列举所有可能性并找到最佳可能性）算法之间的运行时间 .

    • DP算法可以用递归实现，但它们不一定是 .

    • DP算法无法通过memoization加速，因为每个子问题只能解决一次（或称为"solve"函数） .

    回复于
  • 9

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

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

    一个简单的例子是仅通过可以提供解决方案的节点遍历树或图，或者将目前为止找到的解决方案放入表中，这样就可以避免反复遍历相同的节点 .

    这里's an example of a problem that'适合动态编程，来自UVA的在线评判：Edit Steps Ladder.

    我将从“编程”一书中快速简要介绍这个问题分析的重要部分挑战，我建议你看看 .

    仔细看看这个问题，如果我们定义一个成本函数告诉我们两个字符串有多远，我们有两个考虑三种自然类型的变化：替换 - 将单个字符从模式“s”更改为不同的字符在文本“t”中，例如将“shot”改为“spot” . 插入 - 将单个字符插入模式“s”以帮助它匹配文本“t”，例如将“之前”更改为“agog” . 删除 - 从模式“s”中删除单个字符以帮助它匹配文本“t”，例如将“hour”更改为“our” . 当我们将每个操作设置为一步时，我们定义两个字符串之间的编辑距离 . 那么我们如何计算呢？我们可以使用观察来定义递归算法，即字符串中的最后一个字符必须匹配，替换，插入或删除 . 在最后一次编辑操作中删除字符会使一对操作留下一对较小的字符串 . 设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个字符的字符串需要几秒钟，并且计算消失为永远不会落在任何更长的字符串上 . 为什么算法这么慢？它需要指数时间，因为它会一次又一次地重新计算值 . 在字符串中的每个位置，递归分支三种方式，这意味着它以至少3 ^ n的速率增长 - 实际上甚至更快，因为大多数调用仅减少两个索引中的一个，而不是两个 . 那么我们如何才能使算法实用呢？重要的观察是，大多数这些递归调用都是计算之前已经计算过的东西 . 我们怎么知道？好吧，只能有| s | ·| t |可能的唯一递归调用，因为只有许多不同的（i，j）对作为递归调用的参数 . 通过将这些（i，j）对中的每一对的值存储在表中，我们可以避免重新计算它们，并根据需要查看它们 . 该表是二维矩阵m，其中每个| s |·| t | cells包含此子问题的最优解的成本，以及解释我们如何到达此位置的父指针：typedef struct {
    成本; / 到达这个单元的成本 /
    int parent; / 父细胞 /
    } 细胞;

    单元m [MAXLEN 1] [MAXLEN 1]; / 动态编程表 /
    动态编程版本与递归版本有三个不同之处 . 首先，它使用表查找而不是递归调用来获取其中间值 . **其次，**它更新每个单元格的父字段，这将使我们以后能够重建编辑序列 . **第三，**第三，它使用更通用的目标cell（）函数进行检测，而不仅仅返回m [| s |] [| t |] .cost . 这将使我们能够将此例程应用于更广泛的问题 .

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

    Here's对同一问题的替代，完整解决方案 . 它's also a 612845 one even though its execution is different. I suggest you check out how efficient the solution is by submitting it to UVA'在线评判 . 我觉得如此有效地处理这么重的问题是多么惊人 .

    回复于
  • 18

    动态编程的关键部分是“重叠子问题”和“最优子结构” . 问题的这些属性意味着最优解决方案由其子问题的最优解决方案组成 . 例如，最短路径问题表现出最佳子结构 . 从A到C的最短路径是从A到某个节点B的最短路径，接着是从该节点B到C的最短路径 .

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

    • 找到从起始节点到触及它的每个节点的距离（例如从A到B和C）

    • 找到从那些节点到触摸它们的节点的距离（从B到D和E，从C到E和F）

    • 我们现在知道从A到E的最短路径：对于我们访问过的某个节点x（B或C），它是A-x和x-E的最短和

    • 重复此过程，直到我们到达最终目标节点

    因为我们正在自下而上地工作，所以我们已经在使用它们时通过记忆它们来解决子问题 .

    请记住，动态编程问题必须同时存在重叠子问题和最佳子结构 . 生成Fibonacci序列不是动态编程问题;它利用了memoization，因为它有重叠的子问题，但它没有最佳的子结构（因为没有涉及优化问题） .

    回复于
  • 1

    Dynamic Programming

    Definition 动态编程（DP）是一种通用算法设计技术，用于解决重叠子问题的问题 . 这种技术是美国数学家“理查德贝尔曼”在20世纪50年代发明的 .

    Key Idea

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

    Dynamic Programming Properties

    • 使用小实例的解决方案解决实例 .

    • 可能需要多次使用较小实例的解决方案，因此请将结果存储在表中 .

    • 因此每个较小的实例只解决一次 .

    • 额外的空间用于节省时间 .

    回复于
  • 4

    这是来自CMU的Michael A. Trick的一个教程，我发现它特别有帮助：

    http://mat.gsia.cmu.edu/classes/dynamic/dynamic.html

    当然除了其他人推荐的所有资源之外（所有其他资源，特别是CLR和Kleinberg，Tardos非常好！） .

    我喜欢这个教程的原因是因为它逐渐引入了高级概念 . 它有点古老的材料，但它是这里提供的资源列表的一个很好的补充 .

    另请参阅Steven Skiena的页面和动态编程讲座：http://www.cs.sunysb.edu/~algorith/video-lectures/

    http://www.cs.sunysb.edu/~algorith/video-lectures/1997/lecture12.pdf

    回复于
  • -2

    我也是动态编程的新手（针对特定类型问题的强大算法）

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

    Previous knowledge 是最重要的，跟踪你已经存在的子问题的解决方案 .

    考虑一下这个来自维基百科的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） . 在较大的示例中，重新计算了更多的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]

    如果我们还没有，那么我们在 Map 中保存子问题的解决方案 . 这种保存我们已经计算过的值的技术被称为Memoization .

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

    回复于
  • 183

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

    名称建议的动态编程使用先前计算的值来动态构建下一个新解决方案

    应用动态编程的位置：如果解决方案基于最佳子结构和重叠子问题，则在这种情况下使用较早的计算值将非常有用，因此您无需重新计算它 . 这是自下而上的方法 . 假设您需要计算fib（n），那么您需要做的就是添加先前计算的fib（n-1）和fib（n-2）的值

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

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

    回复于
  • 5

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

    The seven steps in the development of a dynamic programming algorithm are as follows:

    • Build 一个递归属性，为问题实例提供解决方案 .

    • 根据递归属性开发递归算法

    • 在递归调用中再次查看是否再次解决了同一个问题实例

    • 开发一个memoized递归算法

    • 请参阅将数据存储在内存中的模式

    • 将memoized递归算法转换为迭代算法

    • 根据需要使用存储优化迭代算法（存储优化）

    回复于
  • 4

    这是斐波那契系列的 Recursive ， Top-down ， Bottom-up 方法的简单python代码示例：

    递归：O（2 ^ n）

    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))
    回复于

相关问题