# 动态规划 > 原文： [https://www.programiz.com/dsa/dynamic-programming](https://www.programiz.com/dsa/dynamic-programming) #### 在本教程中，您将学习什么是动态规划。 此外，您还将发现动态规划和贪婪算法之间的比较，以解决问题。 动态规划是计算机编程中的一种技术，可帮助有效解决一类具有重叠子问题和[最佳子结构](https://en.wikipedia.org/wiki/Optimal_substructure)属性的问题。 这些问题涉及重复计算相同子问题的值以找到最佳解决方案。 * * * ## 动态规划实例 以生成斐波那契数列为例。 如果序列是`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 ``` * * * ## 递归与动态规划 动态规划主要应用于递归算法。 这不是巧合，大多数优化问题都需要递归，并且将动态规划用于优化。 但是并非所有使用递归的问题都可以使用动态规划。 除非像斐波那契数列问题那样存在重叠的子问题，否则递归只能使用分治的方法来解决。 这就是为什么诸如归并排序的递归算法不能使用动态规划的原因，因为子问题不会以任何方式重叠。 * * * ## 贪婪算法与动态规划 [贪婪算法](https://www.programiz.com/dsa/greedy-algorithm)与动态规划类似，因为它们都是优化工具。 但是，贪婪算法会寻找局部最优解，或者换句话说，是贪婪的选择，以期找到全局最优解。 因此，贪婪的算法可能会做出一个猜测，即看起来当时是最优的，但代价很高，并且不能保证全局最优。 另一方面，动态规划会找到子问题的最佳解决方案，然后做出明智的选择，以合并那些子问题的结果以找到最佳解决方案。