某些复杂问题不能简单分解成几个小问题，然后在小问题解的基础上简单综合得到问题的解，这样费时费力，重复度高，问题求解耗时会按问题规模成幂级数增加。动态规划法的基本思想是：引入一个数组，把所有子问题的解存在其中，问题的最后解将从这个序列中得到，往往是选取概率最大的、得分最高的子问题的解综合得到问题的最后解。
动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。
设计一个标准的动态规划算法，通常可按一下两个步骤进行：
-
划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。这若干个阶段一定要是有序的或者是可排序的（即无后向性），否则问题就无法用动态规划法求解。
-
选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。状态的选择要满足无后效性，即无论当前取哪个解，对后面的子问题都没有影响。
网友评论