|
|
|
动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是独立的。
|
|
|
|
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解，每个解都对应于一个值，希望找到具有最优值（最大值或最小值）的那个解。当然，最优解可能会有多个，动态规划算法能找出其中的一个最优解。设计一个动态规划算法，通常可按照以下几个步骤进行。
|
|
|
|
|
|
|
|
|
|
（4）根据计算最优值时得到的信息，构造一个最优解。
|
|
|
|
对一个给定的问题，若其具有以下两个性质，则可以考虑用动态规划法来求解。
|
|
|
|
（1）最优子结构。如果一个问题的最优解中包含其子问题的最优解，就说该问题具有最优子结构。当一个问题具有最优子结构时，表示动态规划法可能会适用，但是此时贪心策略可能也是适用的。
|
|
|
|
（2）重叠子问题。它指用来解原问题的递归算法可反复地解同样的子问题，而不是总在产生新的子问题。即当一个递归算法不断地调用同一个问题时，就说明该问题包含重叠子问题。此时若用分治法递归求解，则每次遇到子问题都会视为新问题，会极大地降低算法的效率，而动态规划法总是充分利用重叠子问题，对每个子问题仅计算一次，把解保存在一个在需要时就可以查看的表中，而每次查表的时间为常数。
|
|
|
