编程 动态规划

动态规划有很多种，但基本思想是一样的。
就是对于一个问题，如果它的解包含了它的子问题的解。（即要解出这个问题就必须解出它的子问题）。那么就可以根据它与子问题的关系得到一个状态转移方程。
但动态规划的意义在于，如果多个子问题都包含相同的“子子问题”，那么这个“子子问题”就会被重新计算很多次，用动态规划，我们把这个“子子问题”的解求出并储存下来，再次遇到的时候就不必再次计算。所以可以省下许多时间。
经典的动态规划题目有：0-1背包、装箱问题等。
这些问题的详细解答分析我就不赘述了，网上有许多资料，LZ可以搜索一下。

搜索一下NOI国家集训队论文