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

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

建立递归属性，给出问题实例的解决方案。 根据递归特性开发递归算法 看看同一个问题的实例是否在递归调用中被一次又一次地解决 开发一个记忆递归算法 查看在内存中存储数据的模式 将记忆递归算法转化为迭代算法 根据需要使用存储对迭代算法进行优化(存储优化)

动态规划是指使用过去的知识来更容易地解决未来的问题。

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

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

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

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

Cormen算法书中有一章是关于动态规划的。而且它在谷歌Books上是免费的!点击这里查看。

记忆是指存储函数调用之前的结果(给定相同的输入，真正的函数总是返回相同的结果)。在存储结果之前，算法的复杂性并没有什么不同。

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

动态规划是解决较容易解决的子问题，并由此建立答案的过程。大多数DP算法将处于贪婪算法(如果存在的话)和指数算法(枚举所有可能性并找到最佳的一个)之间的运行时间。

DP算法可以用递归来实现，但它们不必这样做。 DP算法不能通过记忆来加速，因为每个子问题只被解决(或“solve”函数被调用)一次。

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

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

建立递归属性，给出问题实例的解决方案。 根据递归特性开发递归算法 看看同一个问题的实例是否在递归调用中被一次又一次地解决 开发一个记忆递归算法 查看在内存中存储数据的模式 将记忆递归算法转化为迭代算法 根据需要使用存储对迭代算法进行优化(存储优化)

动态规划是一种在递归算法中避免多次计算同一子问题的技术。

让我们以斐波那契数为例:找到定义的第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)

动态规划

自顶向下——记忆

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

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

如何应用动态规划? 找出问题中的递归。 自顶向下:将每个子问题的答案存储在一个表中，以避免重新计算。 自底向上:找到评估结果的正确顺序，以便在需要时获得部分结果。

动态规划通常适用于具有固有的从左到右顺序的问题，如字符串、树或整数序列。如果单纯递归算法不能多次计算同一子问题，动态规划就没有帮助。

我做了一个问题集合来帮助理解逻辑:https://github.com/tristanguigue/dynamic-programing

简而言之，就是递归记忆和动态规划的区别

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

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

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

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