动态规划
- 基本定义：动态规划是解决具有重叠子问题和最优子结构特性问题的编程技巧，通过存储子问题的结果来提高效率。
- 实际应用：以斐波那契数列为例，动态规划通过存储和利用前两个数字的和来计算序列，避免重复计算。
- 递归与动态规划的关系：动态规划常用于优化递归算法，但适用于存在重叠子问题的情况，与分治法递归（如归并排序）不同。
动态规划是一种在计算机编程中的技巧，有助于高效地解决具有重叠子问题和最优子结构属性的问题类别。
如果任何问题可以分解成子问题，而这些子问题又可以继续分解成更小的子问题，如果这些子问题之间存在重叠，那么可以将这些子问题的解保存下来以供将来使用。通过这种方式，可以提高CPU的效率。这种解决方案的方法被称为动态规划。
这些问题涉及反复计算相同子问题的值，以找到最优解决方案。
动态规划示例
让我们找出斐波那契数列的前5项。斐波那契数列是一个数字序列，其中每个数字都是前两个数字的和。例如，0, 1, 1, 2, 3。在这里，每个数字都是前两个数字的和。
算法
假设n是项数。
1. 如果n <= 1，则返回1。
2. 否则，返回前两个数字的和。
我们正在计算斐波那契数列的前5项。
- 第一项是0。
- 第二项是1。
- 第三项是0（来自步骤1）和1（来自步骤2）的和，即1。
- 第四项是第三项（来自步骤3）和第二项（来自步骤2）的和，即
1 + 1 = 2。 - 第五项是第四项（来自步骤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)
如果键 n 不在映射 m 中
m[n] = fib(n − 1) + fib(n − 2)
返回 m[n]
动态规划的记忆化是一种自顶向下的动态规划方法。通过改变算法工作的方向，即从基本情况开始并朝着解决方案前进，我们也可以以自底向上的方式实现动态规划。
function fib(n)
如果 n = 0
返回 0
否则
var prevFib = 0, currFib = 1
重复 n − 1 次
var newFib = prevFib + currFib
prevFib = currFib
currFib = newFib
返回 currFib
递归 vs 动态规划
动态规划主要应用于递归算法。这不是巧合，大多数优化问题需要递归，而动态规划用于优化。
但并非所有使用递归的问题都可以使用动态规划。除非存在重叠子问题，就像斐波那契数列问题一样 ，否则递归只能使用分治方法来达到解决方案。
这就是为什么像归并排序这样的递归算法不能使用动态规划的原因，因为子问题在任何情况下都不重叠。
贪婪算法 vs 动态规划
贪婪算法与动态规划类似，因为它们都是优化工具。
然而，贪婪算法寻找局部最优解，换句话说，它贪婪地选择一个可能在当前看起来最优的选择，希望找到全局最优解。因此，贪婪算法可能会做出当时看起来最优的猜测，但在后续过程中可能变得代价高昂，不能保证全局最优解。
动态规划则找到子问题的最优解，然后经过明智的选择，将这些子问题的结果组合起来，找到最优解。