动态规划

动态规划是计算机编程中的一种技术，它有助于高效地解决一类具有重叠子问题和最优子结构性质的问题。

如果任何问题都可以分解为子问题，而这些子问题又可以分解为更小的子问题，并且这些子问题之间存在重叠，那么这些子问题的解就可以保存起来以供将来参考。通过这种方式，可以提高CPU的效率。这种解决问题的方法被称为动态规划。

这类问题涉及重复计算相同子问题的数值，以找到最优解。

动态规划示例

我们来计算前5个斐波那契数列项。斐波那契数列是这样一种数字序列，其中每个数字是前两个数字之和。例如：0,1,1, 2, 3。在这里，每个数字都是前两个数字之和。

算法

Let n be the number of terms.

1. If n = 0, return 0.
2. If n = 1, return 1.
3. Else, return the sum of two preceding numbers.

我们正在计算前5个斐波那契数列项。

1. 第一项是0。
2. 第二项是1。
3. 第三项是步骤1中的0加上步骤2中的1之和，即1。
4. 第四项是步骤3中的第三项加上步骤2中的第二项之和，即1 + 1 = 2。
5. 第五项是步骤4中的第四项加上步骤3中的第三项之和，即2 + 1 = 3。

因此，我们得到了序列0,1,1, 2, 3。这里，我们使用了前面步骤的结果，如下所示。这被称为动态规划方法。

F(0) = 0
F(1) = 1
F(2) = F(1) + F(0)
F(3) = F(2) + F(1)
F(4) = F(3) + F(2)

动态规划如何工作

动态规划通过存储子问题的结果来工作，这样当需要它们的解时，它们就在手边，我们无需重新计算。

这种存储子问题值的方法称为记忆化。通过将值保存在数组中，我们可以节省计算我们已经遇到过的子问题的时间。

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]

通过记忆化进行的动态规划是一种自顶向下的动态规划方法。通过反转算法工作的方向，即从基本情况开始，向解决方案迈进，我们也可以以自底向上的方式实现动态规划。

function fib(n)
    if n = 0
        return 0
    else
        var prevFib = 0, currFib = 1
        repeat n − 1 times
            var newFib = prevFib + currFib
            prevFib = currFib
            currFib  = newFib
    return currentFib

递归与动态规划

动态规划主要应用于递归算法。这不是巧合，大多数优化问题都需要递归，而动态规划用于优化。

但并非所有使用递归的问题都可以使用动态规划。除非存在像斐波那契数列问题那样的重叠子问题，否则递归只能通过分治法达到解决方案。

这就是为什么像归并排序这样的递归算法不能使用动态规划，因为子问题之间没有任何重叠。

贪心算法与动态规划

贪心算法与动态规划相似，因为它们都是优化工具。

然而，贪心算法是在希望找到全局最优解的前提下，寻找局部最优解，换句话说，是一种贪心选择。因此，贪心算法可以做出在当时看起来最优的选择，但后来可能代价高昂，并且不能保证全局最优。

另一方面，动态规划会找到子问题的最优解，然后做出明智的选择来组合这些子问题的结果，以找到最最优的解决方案。

不同类型的动态规划算法

1. 最长公共子序列
2. Floyd-Warshall 算法