第七章 动态规划（Dynamic programming）
吼吼吼吼
动态规划是一种结合了完全搜索（complete search）和贪心算法优点的技术。动态规划可以用于解决那些可以划分为局部重合的子问题的问题（可能有点抽象，但是结合作者提供的题会好一点）。
作者说学会理解动态规划是每一个编程竞赛选手职业生涯的里程碑。我也觉得，哈哈。
第一节，还是硬币问题，是时候真正的AC这道题了。这里有些公式不太好展开写，建议看书，略略略。但是提一下关键技巧，其一是递归的定义解，就像我们做数列题递归的定义第n项那种，第二是从递归的定义中寻找可以记忆化的点。作者花了好多页写，慢慢看，很好理解。
第二节，最长递增子序列（Longest increasing subsequence），看书，注意这里的子序列不一定是连续的。作者大大给出了一个O(n^2)的解法，并向你扔出了一个挑战，这个问题有O(nlogn)的解法，你能找到吗>_<
第三节，网格中的路径（Paths in a grid），每个网格都有个正权重，寻找一个从起点到终点的路径使得路径的权重和最大。记忆点在于记忆以某点为终点的路径的最大权重。
第四节，背包问题！！！（Knapsack problems）。给定一系列东西，然后寻找一个合适的子集。背包问题通常可以通过动态规划解决。背包问题种类蛮多的，可以上OI-Wiki上看看，上面收录了一些类型的背包问题，个人感觉还是蛮全的。作者给出的示例问题是给定一系列权重，找出所有可以通过这些权重构造出来的和。
第五节，编辑距离（Edit distance）。看书看书。关键点在于递归公式。经过前面的洗礼，应该来说得到递归公式能够很自然的找出其中的记忆点吧。
第六节，Counting tilings（铺地板），用给定的地板讲地面铺满，问有多少种解法。咋一看去，感觉挺难的，然后作者庖丁解牛一番，秒杀，最后还给出了可以直接计算的公式，虽然说要注意精度，但是可以直接算啊，只能说这些大佬真是太强了。
第八章 Amortized analysis（平摊分析）
-_- 不知道怎么翻译再次+1
本章主要就是讲的一个时间复杂度分析的问题，因为一般的直接的观察代码里面有几个循环、递归什么的已经不够了，还需要自习看看代码的实现。作者举了几个典型的例子。
第一节，双指针（Two pointers method）。说实话，我是被双指针带偏了，作者举了两个例子，第一个是子数组和，这个得是连续的了，而且子数组和得是定值，双指针的移动真的妙，敌退我进。第二个是两数字和为定值，这个问题之前也有过，不过这里用的双指针。好了，回归正题，这两个题的双指针的时间复杂度都为O(n)。主要是学习其中的计算时间复杂度的思想。
第二节，最近的较小元素，就是找到一个元素最近的比它小的元素。
第三节，滑动窗口，记录每个滑动窗口的最小值。这几节都没有给出具体算法，可以自己实现挑战一下，作者思路给的不能再清楚了。啊，对，正题，时间复杂度，还是自己看书吧...
预告
明天的两章分别是区间查询（Range queries）和位操控（Bit manipulation）。
连水两天，真幸苦啊（不是）。马上就要结束基础技巧篇了，激动！！！！