动态规划也用于优化问题。像分治法一样,动态规划通过组合子问题的解决方案来解决问题。而且,动态规划算法只解决一次每个子问题,然后将其答案保存在表格中,从而避免了每次重新计算答案的工作。
问题的两个主要属性表明,可以使用动态规划来解决给定的问题。这些属性是重叠的子问题和最佳子结构。
与分而治之的方法类似,动态规划也将解决方案结合到了子问题上。它主要用于需要反复解决一个子问题的场合。计算出的解存储在表中,因此不必重新计算。因此,在存在重叠子问题的地方需要此技术。
例如,二分查找没有重叠的子问题。而斐波那契数的递归程序具有许多重叠的子问题。
如果可以使用子问题的最优解获得给定问题的最优解,则给定问题具有最优子结构属性。
例如,最短路径问题具有以下最佳子结构属性-如果节点x位于从源节点u到目标节点v的最短路径中,则从u到v的最短路径是从u到x的最短路径和从x到v的最短路径的组合。标准的全对最短路径算法(例如Floyd-Warshall和Bellman-Ford)是动态规划的典型示例。
使用以下四个步骤解决动态规划问题: