动态规划介绍

动态规划也用于优化问题。像分治法一样，动态规划通过组合子问题的解决方案来解决问题。而且，动态规划算法只解决一次每个子问题，然后将其答案保存在表格中，从而避免了每次重新计算答案的工作。

问题的两个主要属性表明，可以使用动态规划来解决给定的问题。这些属性是重叠的子问题和最佳子结构。

重叠子问题

与分而治之的方法类似，动态规划也将解决方案结合到了子问题上。它主要用于需要反复解决一个子问题的场合。计算出的解存储在表中，因此不必重新计算。因此，在存在重叠子问题的地方需要此技术。

例如，二分查找没有重叠的子问题。而斐波那契数的递归程序具有许多重叠的子问题。

最佳子结构

如果可以使用子问题的最优解获得给定问题的最优解，则给定问题具有最优子结构属性。

例如，最短路径问题具有以下最佳子结构属性-如果节点x位于从源节点u到目标节点v的最短路径中，则从u到v的最短路径是从u到x的最短路径和从x到v的最短路径的组合。标准的全对最短路径算法（例如Floyd-Warshall和Bellman-Ford）是动态规划的典型示例。

动态规划解题的步骤

使用以下四个步骤解决动态规划问题：

1. 列出最优解决方案的结构
2. 递归定义最优解决方案的值。
3. 计算最佳解决方案的价值，通常以自下而上的方式。
4. 根据已计算的信息构造最佳解决方案。

动态规划方法的应用

• 矩阵链乘法
• 最长公共子序列
• 旅行商问题