CHAPTER6 动态规划 | shenghai's blog | shxt

[codershenghai]

http://www.zhangshenghai.com/posts/40122/

概念分治法将问题划分成一些独立的子问题，递归地求解各子问题，然后合并子问题的解而得到原问题的解。 动态规划适用于子问题不是独立的情况，也就是个子问题包含公共的子子问题。动态规划对每个子子问题只求解一次，将其结果保存在一张表中，从而避免每次遇到各个子问题时重新计算答案。 动态规划的算法可分为以下4个步骤： 描述最优解的结构。 递归定义最优解的值。 按自底向上的方式计算最优解的值。 由计算的结果构造