六大算法之三：动态规划【转载】

->A4};……; {A1,A2,...,Ai}->Ai+1. 这种方式就是第二数学归纳法。对于Ai+1需要前面的所有前序状态才能完成推理过程。我们将这一模型称为高阶马尔科夫模型。对应的推理过程叫做“动态规划法”。 上述两种状态转移图如下图所示： 能用动规解决的问题的特点 能采用动态规划求解的问题的一般要具有3个性质： (1) 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。 (2) 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。 （3）有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没...阅读全文