这周因为国庆，中秋有好多事，但是学习当然是不能落下的。
这周的算法学习了一点点动态规划，动态规划主要应用于决策性问题，同贪心问题有些许相似，即：
已知问题规模为n的前提A，求解一个未知解B。（我们用An表示“问题规模为n的已知条件”）
此时，如果把问题规模降到0，即已知A0，可以得到A0->B.
如果从A0添加一个元素，得到A1的变化过程。即A0->A1; 进而有A1->A2; A2->A3; …… ; Ai->Ai+1. 这就是严格的归纳推理，也就是我们经常使用的数学归纳法；
对于Ai+1，只需要它的上一个状态Ai即可完成整个推理过程（而不需要更前序的状态）。我们将这一模型称为马尔科夫模型。对应的推理过程叫做“贪心法”。
然而，Ai与Ai+1往往不是互为充要条件，随着i的增加，有价值的前提信息越来越少，我们无法仅仅通过上一个状态得到下一个状态，因此可以采用如下方案：
{A1->A2}; {A1, A2->A3}; {A1,A2,A3->A4};……; {A1,A2,...,Ai}->Ai+1. 这种方式就是第二数学归纳法。
对于Ai+1需要前面的所有前序状态才能完成推理过程。我们将这一模型称为高阶马尔科夫模型。对应的推理过程叫做“动态规划法”。
一般步骤：1.划分阶段 2.确定状态和状态变量 3.确定决策 4.查看边界 。
这周主要学习了区间类动态规划，例如石子合并问题，看起来像是贪心，但应使用动态规划。依次选择最小的能覆盖状态空间的维度集合。能量项链问题，合并方向可以不是顺序合并，就是与石子问题相似的合并类问题。
在一本通的网站上做了一下课后题，有卡顿但是总体来说还是比较成功的。
周六有些事情没能去听同学们的讲课我觉得非常可惜，看了看讲课课件就由衷的感慨还是要去听的，大家都很厉害。
下周又将是繁忙的一周了，在vj上面的题目才做了一点，动态规划还有好几个知识点要学习呢。
