动态规划的基本思想是把求解的问题分成许多阶段或 多个子问题，然后按照顺序求解各个子问题。前一子问题的解为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些可能达到最优的局部解，舍弃其他的局部解。依次解决各个子问题，最后一个子问题的解就是原问题的解。动态规划算法与分治法类似，但是不同的是，在使用动态规划求解问题时得到的各个子问题往往不是相互独立的。由于动态规划算法解决问题往往有重叠子问题的特点，因此为了减少重复计算，不管该子问题以后是否被用到，只要它被