一、基本要素：
1、最优子结构性质：一个问题的最优解包含着其子问题的最优解。
2、重叠子问题性质：自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。
二、基本步骤
1、找出最优解性质，并刻画其结构特征。
2、递归定义最优值。
3、由自底向上的方式计算出最优值。
4、根据计算最优值时得到的信息，构造最优值。
三、典型例题
1、所有点对的最短路径问题。（Floyd算法 ）
2、最长公共子序列问题。
3、求子段和最大值问题。
一、基本要素：
1、最优子结构性质：一个问题的最优解包含着其子问题的最优解。
2、重叠子问题性质：自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。
二、基本步骤
1、找出最优解性质，并刻画其结构特征。
2、递归定义最优值。
3、由自底向上的方式计算出最优值。
4、根据计算最优值时得到的信息，构造最优值。
三、典型例题
1、所有点对的最短路径问题。（Floyd算法 ）
2、最长公共子序列问题。
3、求子段和最大值问题。
