【动态规划3】区间与环形动态规划

在前一节学习了线性动态规划后，本章将会讨论两个稍显复杂模型：区间动态规划，及其变 种环形动态规划。这两类动态规划的特点是，囿于问题本身限制，“某类有序事件中前若干个事 件的子答案”不再能支撑状态转移，我们需要去寻找“从某个元素起到另一个元素结束所包含所 有的（连续）元素的子答案”作为状态。 可以想象，在这个描述下，每个状态会对应于原题序列上的一个区间。区间具有良好的性 质：短的区间可以拓宽成长的区间，相同长度的区间互相不包含。这样，可以把所有状态理解成 DAG，即不会有可以互相到达的局面。基于这个原则，可以思考如何构造转移，并在下列例题中 深入理解区间与环形动态规划。