73.md

动态规划

原文： https://www.programiz.com/dsa/dynamic-programming

在本教程中，您将学习什么是动态规划。 此外，您还将发现动态规划和贪婪算法之间的比较，以解决问题。

动态规划是计算机编程中的一种技术，可帮助有效解决一类具有重叠子问题和最佳子结构属性的问题。

这些问题涉及重复计算相同子问题的值以找到最佳解决方案。

---

动态规划实例

以生成斐波那契数列为例。

如果序列是F(1)F(2)F(3)........ F(50)，则遵循规则F(n) = F(n-1) + F(n-2)）

F(50) = F(49) + F(48)
F(49) = F(48) + F(47)
F(48) = F(47) + F(46)
...

注意，子问题如何重叠，我们需要计算F(48)才能计算F(50)和F(49)。 这正是动态规划大放异彩的算法。

---

动态规划的工作原理

动态规划通过存储子问题的结果来工作，以便在需要它们的解决方案时就可以使用它们，而我们无需重新计算它们。

这种存储子问题值的技术称为记忆。 通过将值保存在数组中，我们节省了计算遇到的子问题的时间。

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

---

递归与动态规划

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

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

这就是为什么诸如归并排序的递归算法不能使用动态规划的原因，因为子问题不会以任何方式重叠。

---

贪婪算法与动态规划

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

但是，贪婪算法会寻找局部最优解，或者换句话说，是贪婪的选择，以期找到全局最优解。 因此，贪婪的算法可能会做出一个猜测，即看起来当时是最优的，但代价很高，并且不能保证全局最优。

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