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

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

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

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

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

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

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

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

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

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

动态规划

定义

动态规划(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))

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

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

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

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

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

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

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