1. 将原问题分解为子问题
2. 确定状态
3. 确定一些初始状态(边界状态)的值
4. 确定状态转移方程
1) 问题具有最优子结构性质。如果问题的最优解所包含的
子问题的解也是最优的,我们就称该问题具有最优子结
构性质。
2) 无后效性。当前的若干个状态值一旦确定,则此后过程
的演变就只和这若干个状态的值有关,和之前是采取哪
种手段或经过哪条路径演变到当前的这若干个状态,没
有关系。
1. 将原问题分解为子问题
2. 确定状态
3. 确定一些初始状态(边界状态)的值
4. 确定状态转移方程
1) 问题具有最优子结构性质。如果问题的最优解所包含的
子问题的解也是最优的,我们就称该问题具有最优子结
构性质。
2) 无后效性。当前的若干个状态值一旦确定,则此后过程
的演变就只和这若干个状态的值有关,和之前是采取哪
种手段或经过哪条路径演变到当前的这若干个状态,没
有关系。