动态规划Schl-4口基本思想：将待求解问题分解成若千个子问题，但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。通过保存已解决的子问题的答亲，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。口基本步骤：①找出最优解的性质，并刻划其结构特征。2递归地定义最优值。3以自底向上的方式计算出最优值。4根据计算最优值时得到的信息，构造最优解。11
11 基本思想： 将待求解问题分解成若干个子问题,但是经分解得到的子问题往 往不是互相独立的。不同子问题的数目常常只有多项式量级。在用 分治法求解时，有些子问题被重复计算了许多次。通过保存已解决 的子问题的答案，而在需要时再找出已求得的答案，就可以避免大 量重复计算，从而得到多项式时间算法。 基本步骤： ① 找出最优解的性质，并刻划其结构特征。 ② 递归地定义最优值。 ③ 以自底向上的方式计算出最优值。 ④ 根据计算最优值时得到的信息，构造最优解。 Sch1-4 动态规划
Sch1-4动态规划基本要素：口最优子结构性质：原问题的最优解包含看子问题的最优解，可以①通过反证法来证明问题具有最优子结构性质。重叠子问题：递归算法求解问题时，每次产生的子问题并不总是2新问题，有些子问题被反复计算多次。对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。口问题的关键在于构造子问题空间。一个经验性规则就是，尽量保持这个空间简单，然后在需要时再扩充宅。12
12 基本要素： ① 最优子结构性质：原问题的最优解包含着子问题的最优解，可以 通过反证法来证明问题具有最优子结构性质。 ② 重叠子问题：递归算法求解问题时，每次产生的子问题并不总是 新问题，有些子问题被反复计算多次。对每一个子问题只解一次， 而后将其解保存在一个表格中，当再次需要解此子问题时，只是 简单地用常数时间查看一下结果。 问题的关键在于构造子问题空间。一个经验性规则就是，尽量保 持这个空间简单，然后在需要时再扩充它。 Sch1-4 动态规划