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

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

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

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

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

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

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

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

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

下面是一个适合动态规划的例子，来自UVA的在线评委:Edit Steps Ladder。

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

Take a good look at that problem, if we define a cost function telling us how far appart two strings are, we have two consider the three natural types of changes: Substitution - change a single character from pattern "s" to a different character in text "t", such as changing "shot" to "spot". Insertion - insert a single character into pattern "s" to help it match text "t", such as changing "ago" to "agog". Deletion - delete a single character from pattern "s" to help it match text "t", such as changing "hour" to "our". When we set each of this operations to cost one step we define the edit distance between two strings. So how do we compute it? We can define a recursive algorithm using the observation that the last character in the string must be either matched, substituted, inserted or deleted. Chopping off the characters in the last edit operation leaves a pair operation leaves a pair of smaller strings. Let i and j be the last character of the relevant prefix of and t, respectively. there are three pairs of shorter strings after the last operation, corresponding to the string after a match/substitution, insertion or deletion. If we knew the cost of editing the three pairs of smaller strings, we could decide which option leads to the best solution and choose that option accordingly. We can learn this cost, through the awesome thing that's recursion: #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 ); } This algorithm is correct, but is also impossibly slow. Running on our computer, it takes several seconds to compare two 11-character strings, and the computation disappears into never-never land on anything longer. Why is the algorithm so slow? It takes exponential time because it recomputes values again and again and again. At every position in the string, the recursion branches three ways, meaning it grows at a rate of at least 3^n – indeed, even faster since most of the calls reduce only one of the two indices, not both of them. So how can we make the algorithm practical? The important observation is that most of these recursive calls are computing things that have already been computed before. How do we know? Well, there can only be |s| · |t| possible unique recursive calls, since there are only that many distinct (i, j) pairs to serve as the parameters of recursive calls. By storing the values for each of these (i, j) pairs in a table, we can avoid recomputing them and just look them up as needed. The table is a two-dimensional matrix m where each of the |s|·|t| cells contains the cost of the optimal solution of this subproblem, as well as a parent pointer explaining how we got to this location: typedef struct { int cost; /* cost of reaching this cell */ int parent; /* parent cell */ } cell; cell m[MAXLEN+1][MAXLEN+1]; /* dynamic programming table */ The dynamic programming version has three differences from the recursive version. First, it gets its intermediate values using table lookup instead of recursive calls. **Second,**it updates the parent field of each cell, which will enable us to reconstruct the edit sequence later. **Third,**Third, it is instrumented using a more general goal cell() function instead of just returning m[|s|][|t|].cost. This will enable us to apply this routine to a wider class of problems.

这里，对收集最优部分结果所需要的内容进行了非常具体的分析，是什么使解决方案成为“动态”解决方案。

这是同样问题的另一个完整的解决方案。它也是一个“动态的”游戏，尽管其执行方式有所不同。我建议你把它提交给弗吉尼亚大学的在线评委，看看这个解决方案有多有效。如此沉重的问题竟能如此有效地解决，我感到惊奇。

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

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

求出从起始节点到触及它的每个节点的距离(比如从A到B和C) 求出这些节点到与其接触的节点的距离(从B到D和E，以及从C到E和F) 我们现在知道了从A到E的最短路径:它是我们访问过的某个节点x的A-x和x-E的最短和(B或C) 重复这个过程，直到到达最终的目标节点

因为我们是自下而上地工作，所以当需要使用这些子问题时，我们已经通过记忆它们得到了它们的解决方案。

记住，动态规划问题必须有重叠的子问题和最优的子结构。斐波那契数列的生成不是一个动态规划问题;它利用记忆，因为它有重叠的子问题，但它没有最优的子结构(因为不涉及优化问题)。

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

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

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

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

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

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

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

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

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

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

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

我对动态规划(一种针对特定类型问题的强大算法)也非常陌生。

简单地说，只需将动态规划视为使用前面知识的递归方法

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

下面是来自维基百科的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]

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

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

动态规划

定义

动态规划(DP)是求解问题的一种通用算法设计技术 带有重叠子问题的问题。这项技术是美国人发明的 数学家理查德·贝尔曼在20世纪50年代。

关键理念

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

动态规划属性

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

下面是一个简单的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))

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

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

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