动态规划的基本思想是把求解的问题分成许多阶段或

多个子问题，然后按照顺序求解各个子问题。前一子问题的解为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些可能达到最优的局部解，舍弃其他的局部解。依次解决各个子问题，最后一个子问题的解就是原问题的解。动态规划算法与分治法类似，但是不同的是，在使用动态规划求解问题时得到的各个子问题往往不是相互独立的。由于动态规划算法解决问题往往有重叠子问题的特点，因此为了减少重复计算，不管该子问题以后是否被用到，只要它被计算过，就将其结果填到表中。动态规划算法适用于解最优化问题，通常可按照四个步骤进行设计：

①找出最优解的性质，并刻画其结构特征　　

②递归地定义最优值

③以自底向上的方式计算最优值

④根据计算最优值时得到的信息，构造最优解

-The basic idea of ​ ​ dynamic programming is to solve the problem into a number of stages or

Multiple sub-problems, and then follow the order of the various sub-problems to solve. The problem before the solution of a son and a son, after solving the problem of providing useful information. Any child in solving problems, list possible local solutions, which may be retained by making the local optimal solution, discard the other partial solutions. In order to solve the various sub-problems, the solution of the last sub-problem is the solution of the original problem. Dynamic programming algorithm and divide and conquer method similar, but the difference is in the use of dynamic programming to solve problems in various sub-problems are often not independent of each other. As the dynamic programming algorithm to solve the problem often have the characteristics of overlapping sub-problems, so in order to reduce double counting, regardless of whether the sub-problem after being u