动态规划动态规划什么是动态规划？（一）动态规划是解决多阶段决策问题的一种方法。多阶段决策问题n 对于整个问题，可以根据其时间或其他顺序分成若干个前后相关联的子问题，问题的全局最优包含其子问题的局部最优，即满足最优子结构性质，并且无后效性，有边界条件，且一般划分为很明显的阶段，存在一条或多条状态转移方程。“最优性原理”可陈述为：不论初始状态和第一步决策是什么，余下的决策相对于前一次决策所产生的新状态，构成一个最优决策序列。 最优决策序列的子序列，一定是局部最优决策子序列。 包含有非局部最优的决策子序列，一定不是最优决策序列。最优性原理 如图，已知一个有向图，求一条从最左边的点走到最右边点的方案（只能从左往右走），使得所经过的权值和除以4的余数最小。MOD 4余数最小问题 设所有点从左至右编号为1 4，MIN（i）表示前I个点的最优值，很容易得出一个方程： Min(i)=min(Min(I-1)+numI-1,1) mod 4, Min(I-1)+numI-1,2) mod 4 通过这个方程可以求出一条路径为（2+3+1）MOD 4=2但最优值实际上是 （2+1+1）MOD 4=0。 为什
