应用条件 最优子结构性质 如果问题的最优解所包含的子问题的解也是最优 的,我们就称该问题具有最优子结构性质。 不符合最优子结构性质则不能使用动态规划(用了会 得到错误的解) 子问题重叠性质 每次产生的子问题并不总是新问题,有些子问题 会被重复计算多次。保存中间计算结果而不是重复计 算 不符合子问题重叠性质则使用动态规划不能带来算法 效率的提高应用条件 „ 最优子结构性质 如果问题的最优解所包含的子问题的解也是最优 的，我们就称该问题具有最优子结构性质。 不符合最优子结构性质则不能使用动态规划（用了会 得到错误的解） „ 子问题重叠性质 每次产生的子问题并不总是新问题，有些子问题 会被重复计算多次。保存中间计算结果而不是重复计 算。 不符合子问题重叠性质则使用动态规划不能带来算法 效率的提高