动态规划算法 CR 算法总体思想 动态规划算法与分治法类似，其基本思想也是将待求解问题 分解成若干个子问题 ⊕ 与分治法的区别在于 适用于动态规划算法求解的问题，经分解得到的子问题往 往不是互相独立的；若用分治法求解，则分解得到的子问 题数目太多，导致最终解决原问题需指数时间， 原因在于：虽然子问题的数目常常只有多项式量级，但在 用分治法求解时，有些子问题被重复计算了许多次 ⊕ 如果可以保存已解决的子问题的答案，就可以避免大量重复 计算，从而得到多项式时间的算法 动态规划法的基本思路是：构造一张表来记录所有已解决的 子问题的答案（无论算法形式如何，其填表格式是相同的）动态规划算法  算法总体思想  动态规划算法与分治法类似，其基本思想也是将待求解问题 分解成若干个子问题  与分治法的区别在于 ━ 适用于动态规划算法求解的问题，经分解得到的子问题往 往不是互相独立的；若用分治法求解，则分解得到的子问 题数目太多，导致最终解决原问题需指数时间， ━ 原因在于：虽然子问题的数目常常只有多项式量级，但在 用分治法求解时，有些子问题被重复计算了许多次  如果可以保存已解决的子问题的答案，就可以避免大量重复 计算，从而得到多项式时间的算法  动态规划法的基本思路是：构造一张表来记录所有已解决的 子问题的答案（无论算法形式如何，其填表格式是相同的）