第二章 初出茅庐——初级篇：暴搜、贪心与DP

UPD：写完DP这个章节后，发现根据自己的经验和想法能延伸出来更多内容，例如某些问题的其他解法、算法的分析和推导过程、严谨的正确性证明等等，核心目标都是为了更好地理解书中知识和融会贯通。DP和贪心涉及的一些例题也很不错，值得一写，后续会在末尾补充书中部分习题的代码。
因此“初出茅庐”篇应该会被组织为四篇，第一篇为“暴搜、贪心和DP”，这三个主题本身也是相互关联非常大的部分；第二篇为“数据结构与图论(一)”，把这两类结构化相关的专题打包，其中图论部分内容会比较多；第三篇为“数学”，因为本人数学极差，作为学好数学类型题目的开端，可能会写得比较啰嗦；第四篇为“GCJ题目和练习题”，侧重解法。

从第二章开始内容就多了起来，由于以后可能会有很多东西想写，所以尽可能压缩篇幅，这本书还是以每一章总结一篇文章，瀑布流可以让内容更加内聚，不会太过分散；而且这本书是每个章节对应一个练习题集，整体来看题目数量是比较少的，所以一章一篇总结是合适的

最基础的“穷竭收缩”

搜索这里大概脉络是：

1. 介绍了递归函数：自己调用自己
2. 通过斐波那契数列问题，引出记忆化搜索保存重复运算的结果的思想
3. 通过“部分和问题”和“园子积水问题”(本质是图搜索)，说明DFS
4. 通过“迷宫最短路径”问题，说明BFS
5. 介绍了C++中求 \(n!\) 的函数next_permutation，介绍了剪枝的思想

下面对其中一部分有趣的地方做一些说明

递归函数和斐波那契数列

斐波那契数里的定义如下：
\(\begin{cases} a_0 = 0 \\ a_1 = 1 \\ a_n = a_{n-1} + a_{n-2} \end{cases}\)

所以使用递归可以很方便的求解\(a_n\)：

int fib(int n) {
	if(n <= 1) return n;
	return fib(n - 1) + fib(n - 2);
}

但是展开以后可以发现fib这个函数调用次数是指数级的，拿fib(10)来说，fib(10) = fib(9) + fib(8)，fib(9) = fib(8) + fib(7)，也就是计算(或者说调用)一遍fib(10)需要计算两遍fib(8)；而计算一个fib(8)则需要计算两遍fib(6)；对于奇数情况我们从fib(9)展开，可以得到同样的结果

即：计算一个fib(n)需要计算2遍fib(n-2)，展开以后会发现，计算一个fib(n)需要计算\(2^k\)遍fib(n-2*k)，因此算法是指数级的

使用一个数组保存计算结果可以避免重复计算，这是记忆化搜索和动态规划速度快的原因：

int memo[maxn];
int fib(int n) {
	if(n <= 1) return n;
	if(memo[n] > 0) return memo[n];
	return memo[n] = fib(n-1) + fib(n-2);
}

除了斐波那契数列外，对gcd等也可以用同样的方法优化

深度优先搜索

最开始学深搜的时候，是大学做了八皇后那道题目，对于第一次接触递归的同学来说dfs还是比较难理解的，需要在脑海中不停反复模拟搜索过程，习惯了以后才能应用自如

具体到这本书中的内容，深搜涉及到两个典型应用：

1. 枚举：对应的问题是“部分和问题”，n个数字中，能否选取若干数使其和为k，其中n <= 20
   考虑每个数加或不加，枚举所有的方案，对每个方案计算和是否等于k即可。方案总数有\(2^n\)个，每个方案对应dfs最终的一个搜索节点，因此时间复杂度也是\(O(2^n)\)
   这里可以扩展一下，如果n <= 40，原本的做法会超时，这时候可以使用“中途相遇法(meet-in-the-middle)”来解：将前n/2个数和后n/2个数分为两波，各自枚举方案，并将各自方案的sum保存在数组中，对其中一个数组a排序，遍历其中一个数组b，并且用二分在排好序的数组a中查找k-sum。这样的复杂度为：\(O(2^{n/2}log2^{n/2})\)，“枚举+排序”和“枚举+查找”均为这个复杂度
   另外还有一种做法，就是将a和b数组均排序，从小到达枚举a数组，对当前的\(a_i\)，从大到小枚举b数组中的\(b_j\)，保持\(a_i + b_j >= k\)，可以发现下标i单调递增，下标j单调递减，整个过程的复杂度是\(O(n)\)的(尽管“枚举+排序”的复杂度仍是\(O(2^{n/2}log2^{n/2})\))，理论依据是，两个数的和(基本)不变，一个数增加，另一个数要减小，这种方法叫做“尺取法”，也叫做“two pointers”

2. 搜图：对应“园子积水”问题，更普遍的叫法是“连通块”问题，给出一个M*N的矩阵，其中'W'代表水，'.'代表陆地，每个单元和周围8个相邻单元连通(也有些题目规定4个共边单元)，问矩阵中一共有多少个连通块
   书中的做法是使用dfs以某个'W'单元为入口进行搜索，进入该单元后，会将该单元设置成'.'，这样后面的单元就不会重复访问这个单元了，随后向周围8个方向搜索，由于'W'越来越少，最终一定会结束。每次这样的搜索过程都伴随着一个连通块的消失，因此搜索次数就是连通块数
   之前学过的搜图过程，都是打vis标记来“判重”，而这次直接把到达的单元“删掉了”，看似合理且符合直觉，但是不禁要问一声：WHY？如何证明这样的过程是对的呢？(下面的证明过程比较毒瘤，“算感”强的意识流选手可以直接跳过)
   当思考打vis标记来判重的过程时，仿佛也碰到了同样的问题，所以我们需要证明：dfs可以到达连通块中的每个元素，尽管它看上去显然成立，是属于数学中“这也要证？！！”的类型
   这里的矩阵实际上属于图(ghaph)的范畴，一个'W'单元就是一个节点，'W'和周围8个相邻的'W'之间存在无向边，所以一个连通块对应一个无向连通图
   那么dfs可以到达无向连通图中的每个点吗？考虑dfs进入一个node的过程：1). 先打vis标记； 2). 对周围能到达且没打vis标记的节点进行dfs；
   所以是否存在一个无向图，经过dfs后，其中某些节点没有到达？显然，不可能所有节点都没有到达，因为我们从某个入口进去了；因为图是连通的，所以我们一定能找到一个没有到达的节点v与某个到达过的节点u相连，在节点u退栈之前，根据上述dfs的搜索步骤，一定会进入节点v
   对于“删点”的做法也有同样的证明方法，因此一个连通块不可能存在没被删掉的点

这块的证明看似又绕又没有必要，但是很好的回答了一个“这也能证？！！”的问题。

宽度优先搜索

宽搜比深搜更加直观，列举了一个“迷宫最短路径”问题；从“源点S”到“终点G”，一层一层的将新的节点加入到队列中去，这个过程就像一颗石头砸到平静的水面上
宽搜和深搜如果需要保证复杂度为\(O(n)\)就必须保证每个点只“访问”一次，对宽搜而言，“访问”对应着从队列中取出来的那部分操作
跟深搜一样，宽搜我们要选一个入口，这个点进入队列后要标记它，防止对它重复访问，“入队时标记”的原因是，有可能同一层次的多个节点会到达下个层次的同一个节点
“所有第k层的点能一步到达的未被访问的节点为第k+1层的节点”，这样一层一层的扩展顺序总能保证到每个点的距离最短，就像高低不同的台阶

一切其他需要注意的地方

1. 有些特殊状态的枚举有其专门的方法：例如\(n!\)可以使用next_permutation枚举、二进制在\(O(3^n)\)枚举集合子集、据说位运算还能枚举\(C_n^k\)
2. 书中只是介绍了剪枝，是说需要经过n步的决策生成方案，决策到第k步时发现剩下的n-k步无论作出什么决策方案都是非法的，那就可以不继续向下了；对应到“状态搜索树”中就是剪掉了一个子树。需要注意的是，按照什么策略去剪枝，是可以很灵活很深入的内容，刘汝佳的书里提到的一些UVa题目中很考研剪枝的策略选取，只是不确定这类题目如今是否流行
3. 需要计算某些状态的最小解的时候，经常将状态初始化为INF，而在dp的刷表法中，经常会遇到d[i][j] = min(d[i][j], d[i][k] + x)这样的写法，如果INF取得太大，可能会溢出导致WA，所以INF如何取到既大于所有合法解，又不会在运算中导致溢出，也需要探索(可能没有最好的办法，只能引入标记或者-1特判解决)
4. 怎么将递归写成循环形式，也是一个没有掌握的专题

一直往前！贪心法

脉络上先对贪心的“定义”进行介绍，随后通过几道例题来说明贪心法的应用；

贪心的重点

1. 首先是定义：贪心是基于当前现状，遵循某种确定的规则进行决策，决策后会转移到新的状态，再根据新的状态应用相同的规则来决策，状态的转移是确定的一条链，这也是为什么说贪心法是“一直向前”；
2. 使用贪心法做决策不像动态规划，动态规划是从多个决策中找其中最优的选择，多个决策它都要走一遍，具备一定的“枚举”性质；
3. (个人对贪心的理解)使用贪心思想解题的时候，分析问题的角度可以尝试着去贴近直觉和“常识”，当然也有需要先进行分析，找到单调性等其他性质来作为贪心的依据；
4. 贪心的证明方法大多采取“反证法”，典型的过程是：对比贪心法生成的解(或决策步骤)和假定当中的最优解，逐步证明“假定最优解”的当前这步按照贪心去做不会变得更差(这个在下面例题中会体现)

证明算法正确性是否重要

1. 大胆猜测，无需证明。——来自某OI高中选手
2. 反正我过了。——来自队友
3. 在考试的时候，想到一个算法以后，心里会大致有个约莫，百分之七八十，或者百分之五六十，就可以尝试交一下。——来自yxc的某次直播(确切的话记不住了，但大约是这个意思)
4. 在程序设计竞赛中，只要程序能够正确运行就好了，严格意义上的证明不是必须的。因此可以说，有足够自信的话是不需要证明的。——来自本书作者

所以不只一个人反复的告诉我，程序设计竞赛的重点在于“算法设计”而不是“正确性证明”，因为赛场上可能不会有那么多的时间。当然，如果无法确定WA是算法有问题还是代码实现的问题，思考一下证明也是好的。

题目讲解(贪心的思想要通过具体问题体现)

1. 简单的硬币问题：有面额为1, 5, 10, 50, 100, 500的硬币，求支付A元时，最少需要使用多少个硬币。
   按直觉来说，应该优先从高面额到低面额尝试，因为存在1，所以一定能凑够A元。正确性在于，低面额的硬币“合成”为高面额的硬币会让答案更优，因此能合成时一定要合成，当无法合成时到达最优解。

2. 区间调度问题：有n项工作，每项工作从\(s_i\)开始，到\(t_i\)结束，不能同时做2项工作(时刻不能重合)，问最多能做多少项工作。
   按直觉来说是优先做最早能完成的那个工作，然后就可以尽快做下一个，之后的工作也都按照这个策略来；作者在这里也猜测了其他的策略，但是都通过反例否定了；我们在做贪心的题目的时候，往往也会经历这样一个猜策略的阶段，然后发现猜的策略都不对，正确的策略往往都更复杂一些
   严格证明需要用到反证法：假设存在一个解，比按照贪心法生成的解可以做更多的任务。按照每个任务的结束时间排序为\((b_1, b_2, ..., b_n)\)，贪心法生成的解，按照每个任务结束时间排序为\((a_1, a_2, ..., a_m)\)，其中\(m < n\)。
   考虑第一个元素，\(t_{a_1} <= t_{b_1}\)，因此我们使用\(a_1\)替换\(b_1\)一定满足约束，且不会使结果更差，当前b变成了\((a_1, b_2, ..., b_n)\)；按照序列\(a\)的定义，有\(t_{a_2} <= t_{b_2}\)，因此可以继续向后替换，最终，序列\(b\)会变成：\((a_1, a_2, ..., a_m, b_{m+1}, ..., b_{n})\)，按照序列\(a\)的生成法则，不会存在某个元素\(k\)满足\(k_x > t_{a_m}\)，因此不可能存在这样的序列\(b\)

3. (POJ 3617) Best Cow Line：一个长度为N的字符串S，构造字符串T，每次从N头或尾摘一个字符append到T，求字典序最小的T
   因为N <= 1000，我们可以允许\(O(n^2)\)的做法；当头尾两个元素不一样的时候，显然应该选择较小的，我们考虑两者一样的时候怎么办。一定会对比下一个，如果下一个一样再继续向下对比，因此如果S是一个回文串意味着当前这一步从前往后还是从后往前取都是一样的；
   在第一次碰上了两个不一样元素的时候，直觉上应该这两个元素哪个小就从哪边取，因为这样可以使我们更早地取到这个较小元素，而作者也讲到这里，并没有给出证明，我们来看看能否(较为)严格地证明它
   最笨的方法是分类讨论，假设头尾第一个元素相等为\(X\)，左侧第二个元素为\(p\)，右侧第二个元素为\(q\)，那么当\(p > X\)且\(q > X\)时，我们头两个元素都需要取X才最优，也就是这种情况左右从谁先取都一样；
   即，当\(min(p, q) > X\)，从哪边取都可以；
   然后再考虑剩下的情况：
   当\(min(p, q) < X\)，且 \(p \neq q\)时，第一个元素为\(X\)，第二个元素一定为\(min(p, q)\)；
   当\(min(p, q) < X\)且\(p = q\)，这种情况继续向下找，直到该条件不成立；
   当\(min(p, q) = X\)且\(p = q\)，这种情况跟上面的情况一样，继续向下找，直到条件不成立；
   当\(min(p, q) = X\)且\(p \neq q\)时，不妨设\(p > q = X\)，此时第一个元素为\(X\)，如果第二个元素取\(p\)(即从左边取)，在\(q\)下一个元素 \(< X\)时会丢失最优解；但是第二个元素取\(q\)时，即使\(q\)的下一个元素\(> X\)也没有关系，因为我们要取完之间的所有X，因此第二个元素取\(q\)永远不亏；
   让我们继续考虑向下找的情况，一旦条件不成立后会发生什么，可以注意到，此时左右两侧均为单调非增，所以一旦开始从一侧取，在这个单调非增区间内几乎都会选择从这一侧取
   可以发现尽管分析了一通，想找到严格证明还真是个精细活，上面的内容并不足以严格证明这套算法，但是当我们把目光放宽泛一些的时候，好像又有一些新的发现：
   正确且严谨的证明，从第一个碰到的不相等的\(s_k\)和\(s_{n-1-k}\)中的较小一侧取是最优解：
   设\(s_k\)与\(s_{n-1-k}\)是左右两侧对比第一个不相等的元素，不妨设\(s_k>s_{n-1-k}\)，这意味着：\(s_0s_1...s_{k-1}\)与\(s_{n-1}s_{n-2}...s_{n-k}\)相等，我们将这个字符串表示成：\(a_0a_1...a_{k-1}s_k...s_{n-1-k}b_{k-1}...b_1b_0\)，其中\(a_i = b_i\)
   假设存在一个最优策略去取，当第一次碰到\(s_k\)或\(s_{n-1-k}\)时，一定是下列场景之一：
   1). \((a_ja_{j+1}...a_{k-1})(s_k)(...)(s_{n-1-k})\)
   2). \((s_k)(...)(s_{n-1-k})(b_{k-1}b_{k-2}...b_{k-j})\)
   3). \((a_k)(...)(a_{n-1-k})\)
   如果是第3)种场景，由对称性，可以发现第一步从左侧还是右侧取并无差别；
   如果是第2)种场景，考虑继续向后取的操作：一种是在取\(s_k\)之前取完了所有的\((b_{k-1}b_{k-2}...b_{k-j})\)，这样会转移成第3)种场景；另一种是在取完所有的\((b_{k-1}b_{k-2}...b_{k-j})\)前取了\(s_k\)，可以发现这种一定不是最优解，因为我们可以构造出来一种对称的场景\((a_{k-j}...a{k-2}a_{k-1})(s_k)(...)(s_{n-1-k})\)，按照相同的步骤去取，只不过用\(s_{n-1-k}\)替换了\({s_k}\)，但是得到了更优的答案；
   如果是第1)种场景，我们取了\(a_0,..., a_{j-1}\)和\(b_0, ..., b_{k-1}\) (\(j < k\))，他们在满足\(a\)和\(b\)各自顺序的情况下构成了一个序列，如果第一步取的是\(a_0\)而不是\(b_0\)，我们可以将所有的\(a_0,..., a_{j-1}\)和\(b_0, ..., b_{j-1}\)互换，由于\(a_i = b_i\)，结果不变；
   综上所述，在\(s_k < s_{n-1-k}\)时，我们总可以先取\(b_0\)。
   在百度上搜了这道题目，很多人不知道严格证明的，而实际上这个证明我也搞了一上午(一开始沿着错误的方向尝试了比较久)，可见完成一道算法的严谨证明是多么困难的一件事，赛场上基本是不可能完成的
   但是从这个题目的证明过程，我总结了两点可能有用的思想：
   1). 在寻求思路阶段，不要过度陷入到细节当中，类似“迭代加深搜索”，时常回过头来醒醒神，回溯出来，看看是否有更好的方向
   2). 同样在寻求思路阶段，要把眼光放长远一些，可能从问题的大概轮廓上就能找到正确的方向(对这个问题就是从两侧都是回文着手，碰到第一个打破回文的位置，结合对称性开始研究)
   3). 在方向确定后，需要向“具体”的层面去走，最好用数学定义问题，利用数学解决问题(对本问题就是定义出了第一个打破回文位置的字符串的形式，找到了合适的符号去描述对称)
   我们回过头来看这篇证明，就显得非常学术，但是搞竞赛不是搞学术，如何更快更好的找到思路，设计出算法才是核心(是的我现在不怕提到快这个字了，毕竟SRM一场75分钟，基本是没思路连罚坐机会都不给就结束的节奏)

4. (POJ 3069) Saruman's Army：直线上有N个点，可以给其中若干点打上标记，舍得其自身及左右距离R以内的点被笼罩，问使得N个点全部被笼罩至少需要给多少个点打上标记
   这题跟区间调度问题类似，每次找到最晚的点(尽量靠右的边界)覆盖住之前所有点即可，证明思路和过程也完全一样

5. (POJ 3253) Fence Repair：一个长木版要切成\(L_1, L_2, ..., L_n\)大小的木板，每次切割时，需要花费当前被切割的木板长度那么大的代价，问完成整个任务的最小开销
   时光倒流法 + 哈夫曼的一道题目，关键是从结果思考问题：任何方案在最终都是会将模板木版拆成\(L_1, L_2, ..., L_n\)，如果我们将拆分的过程描述出来，无论过程是什么样的，一定会构成一个二叉树结构，除了叶子结点外，每个节点都代表着一次拆分；设根节点深度为0，则答案是\(\sum_{i=1}^nL_idepth_i\)
   虽然树的结构不同会对应不同的一组\(n\)个\(depth_i\)，但是对任何一个二叉树结构，将最小值\(L_{min}\)和次小值\(L_{sec}\)放在深度最深的位置总没错
   用反证法容易证得，一定存在一个最优解满足最小值\(L_{min}\)和次小值\(L_{sec}\)放在深度最深且其父节点相同的两个叶子结点上
   如果存在一个不符合上述条件的最优解小于所有符合上述条件的解，我们可以通过将\(L_{min}\)和\(L_{sec}\)对应节点交换到深度最深且其父节点相同的两个叶子结点上不会更差来证伪
   一旦这两个节点的父节点相同，则在其拆分之前均为一个整体(其父节点到根节点路径上的每次拆分这两个节点都共同参与)，因此可以将其视作合并，这样问题就转化为了一个规模为\(n-1\)的相同问题，直到规模收敛为1，得出答案
   哈夫曼编码也是同样的思想

记录结果再利用的动态规划

这一节内容更为高深，DP问题应该是算法竞赛当中核心的核心，后期难度较高的DP问题我猜测都是考察想象力，即能否得出正确的DP转移方程；但是这节内容也可以看到有逐步分析化简得来的DP，其中利用数学式子推导出等价转移关系的部分尤其精彩(也望而生畏)

01背包与记忆化搜索

共有\(n\)个背包，每个背包有重量\(w_i\)和价值\(v_i\)，问挑选总重量不超过\(W\)的物品，最大价值能为多少

1. 最直接的方法还是暴搜，通过枚举每个物品是否选择来生成所有的方案，并对每个方案判断合法性，共计有\(O(2^n)\)个方案总数，对于\(n <= 20\)是可行的；
2. 可以将这\(n\)个物品分为两组，分别枚举方案，每组各有\(O(2^{n/2})\)种方案，对第二组方案按照总重量排序\(weightb_i <= weightb_{i+1}\)，并且按照前缀处理出对应的数组\(value_i = min\{value_j | j <= i\}\)，对第一组当中的每个方案(假定该方案选取物品总重量为\(weighta_i\))，二分查找找到第二组方案中的\(max\{j |weight_j <= W-weighta_i \}\)，对应的\(value_j\)就是能与第一组方案中当前方案搭配的第二组方案的最大价值；时间复杂度为\(O(2^{n/2}log2^{n/2})\)，中途相遇法对于\(n <= 40\)是可行的；
3. 枚举所有的方案并不是必须的，我们设状态\(rec(i, j)\)为：把前\(i\)个物品放入大小为\(j\)的背包时能收获的最大价值，可以发现\(rec(i+1, j) = max(rec(i, j), rec(i, j - w_{i+1}) + v_{i+1})\)(从递归角度写为\(rec(i, j) = max(rec(i-1, j), rec(i-1, j - w_{i}) + v_{i})\)更合适)，因此我们可以通过下面这个递归函数来计算结果，由于对应同样一个状态\(rec(i, j)\)结果只需要计算一次，可以单独开一个数组记录计算结果来避免重复计算，这就是记忆画搜索，复杂度\(O(nW)\)，可以支持较大的\(n\)：

int rec(int i, int j) {
	if(i <= 0) return 0;
	if(j < w[i]) return rec(i-1, j);
	return max(rec(i-1, j), rec(i-1, j-w[i]) + v[i];
}

关于DP的理解(发散讨论)

这部分讨论基本包含了我对DP原理的所有理解，也很好地解释了为什么DP可以这么快。

1. 可以发现在上面的递归函数中，每层会调用下层的2次递归函数，因此不加记忆化的话，时间复杂度是\(O(2^n)\)级的。
   这会引发一个思考：不考虑记忆化，站在枚举角度，每层都做了2次决策，所以才有了\(O(2^n)\)个节点，这和暴搜的区别在哪？为什么暴搜不能记忆化？(下面的回答是我关于DP的一些理解，只是一些想法记录了下来，日后对DP的理解更上一层楼以后再来填坑)
   因为暴搜是枚举所有方案，确切说，暴搜每层做的决策都会先保存下来，等到\(n\)层决策都做完以后再做判断。每层递归都只做本层决策，与上下层的决策没有任何交互；而记忆化搜索的递归函数，每层都用到了下层的计算结果(对子结构有依赖)；
   同时暴搜也有简单粗暴的优点，由于它枚举了所有可行方案，因此对其他条件没有依赖，比如\(W\)；而对记忆化搜索，重量\(w\)作为DP的一个维度，是“状态空间”的一部分(与具体问题结合得更紧密)，而\(W\)的规模将状态空间约束在了一个较小的范围内(状态的规模有限)；

2. 一个很反直觉的事情是，一共有\(O(2^n)\)种方案，我们难道不需要将所有方案都过一遍才能算出最终结果吗？怎么会有复杂度低于它的算法存在呢？因为\(O(2^n)\)是完整方案的总数，当利用DP建立起来“利用子结果”的条件后，我们需要的只是子结果当中最优的那一个，不是最优的我们没有保存在状态中，因此不需要考虑它们，我们并没有走到所有的完整方案当中；从这个角度理解很像剪枝，只不过我们把最优解以外的解都剪掉了，即子结果若都不可能最优，总体结果就不可能是最优解；这或许就是DP的最优子结构性质(最优解问题中，多个子结果被一个状态取最优值；计数问题中，多个子结果被一个状态统计；都是压缩的思想)
   换一个理解方式来回答这个问题：
   1). 假设在较小范围计算的本质也是枚举(在现实计算中也是这样，比如最下面一层的计算)，枚举的规模相对\(n\)来说很小；即：即使完全枚举也不需要那么耗时；
   2). 而这些较小范围的模枚举结果中，对每个特征值(即：状态)只有一个最优结果能够“向上层传递”(压缩的力量)；
   3). “只有一个最优结果能够向上层传递”在上层视角看来就是：上层在做决策时也不需要依赖于每个子方案，依赖的只是某个特征值(即：状态)对应的最具有代表性的(最优的)解；
   更奇妙的是，被利用的子结果也以相同的方式使用了它的子结果；因为每层的计算结果经过压缩、汇总、取最优后提供给上一层(多对一，本层的多对应上层的一，经过了一次压缩)，而上层基于下层压缩后的结果再进行汇总出本层的结果提供给上上层，而每层的计算结果都被约束在状态空间内，最终的时间复杂度就是状态空间的规模。

首先初始化层(最底层)的状态空间我们已经知道答案了，根据状态的定义就可以确定(一般要么是0要么是-1或者inf)；
然后第一层经过枚举，将最优的答案保存下来，本层计算后每个状态的最终结果是经过枚举后的最优结果，这样上一层再计算的时候只取这个最优结果即可；即每层只计算一遍，上层即使想获取所有方案数也没有机会了，对应于同一个状态的多个具体方案最终只会保留下来最优的一个

凭借上述分析，记忆化搜索或者DP做到了可以不用关心具体的每一种方案，它们关心的是“能代表一类方案的最优解”或“能代表一类方案总数量”的一个状态，这个状态将原本的一组具体方案，按照某几个维度(或叫做特征值)压缩了起来取了最优或累加了计数：例如，\(dp[i][j]\)代表从第\(i\)到第\(n\)个物品选取，总重量不超过\(j\)的最大价值；

可以发现，对于01背包的这一题，站在“我们需要的只是子结果当中最优的那个”的基础上，如果不限制重量，我们可以将算法从\(O(2^n)\)优化至\(O(n)\)(尽管这显得有点蠢，因为这样我们每个都拿就好了)；当加上重量条件时，状态空间和状态转移(这个和具体问题耦合在一起，也是DP设计的难点)也发生了相应改变，最终得到了一个\(O(nW)\)的算法

状态转移的不同方式(不同方向)

对于01背包这个问题，当我们设计出了状态空间和转移方程后，会发现递归不是必须的，转移方程中含有计算顺序：
\(\begin{cases} dp[0][j] = 0 \\ dp[i][j] = max(dp[i-1][j], dp[i-1][j-w_i] + v_i) \end{cases}\)
状态\(dp[i][j]\)的含义是，从前\(i\)个物品中选取总重量不超过\(j\)的物品能获取的最大值
最终答案是\(dp[n][W]\)，并且这个方程通过外层\(i\)，内层\(j\)的双重for循环就很容易实现
(这里跟书本上的方程不一致，因为下标\(i\)的含义不同，我这里的\(v_i\)对应作者的\(v_{i-1}\)，作者好像习惯下标从\(0\)开始，但不是任何时候这样都方便)

我们会发现对相同的问题，如果我们定义不同的状态，会得到不同的方程，例如：
\(\begin{cases} dp[n][j] = 0 \\ dp[i][j] = max(dp[i+1][j], dp[i+1][j-w_i] + v_i) \end{cases}\)
状态\(dp[i][j]\)的含义是，从前\(i\)到第\(n-1\)物品中选取总重量不超过\(j\)的物品能获取的最大值，注意这里\(i\)的下标从0开始
这也是对应起初记忆化搜索递归函数的转移方式，最终答案是\(dp[0][W]\)，外层\(i\)从\(n-1\)到\(0\)，内层由于没有使用滚动数组，计算顺序不做要求(滚动数组会在下面的内容中出现)

作者还有一种更反人类的表达(不能光我一个人觉得恶心)：
\(\begin{cases} dp[0][j] = 0 \\ dp[i+1][j+w_i] = max(dp[i][j+w_i], dp[i][j] + v_i) \end{cases}\)
从前\(i\)个物品里取重量不超过\(j + w_i\)的物品的最大值()

虽然不同的方程对应着不同的计算顺序，但原则上应该是可理解性优先，目前还不清楚第三种写法能带来什么实际好处

填表法、刷表法

这部分内容紧接着上一部分，不同的方程对应着不同的计算顺序，我们实现程序的时候需要严格按照方程的指引，求当前这层的值(未知)需要使用上层的计算结果(已知)，这种做法叫做“填表法”
实现上还存在另一种做法，当我们求得本层结果时，利用本层结果(已知)计算下层结果(未知)，这种做法叫做“刷表法”
填表法和刷表法都是实现层面的选择，它与算法本身关系不大，如果我们把计算结果表示成一个二位表格，填表法对应着已知层(上一层)的多个状态指向未知层(这一层)一个状态的箭头；而刷表法对应着已知层(这一层)的一个状态指向未知层(下一层)多个状态的箭头，两者本质没有任何差别，只是视角不同(“填表法”站在箭头的终点，“刷表法”站在箭头的起点)

更难的DP问题

后面出现了更多更复杂的一些DP问题，有些对应完全不同的模型，有些需要通过数学将公示化简来得到新的转移方向：

1. 最长公共子序列问题(LCS)
   给定两个字符串\(s_1s_2...s_n\)和\(t_1t_2...t_n\)，求他们的最长公共子序列长度(子序列不是子串，元素可以不连续)。
   定义\(dp[i][j]\)为字符串\(s_1...s_i\)与字符串\(t_1...t_j\)的LCS长度，则转移方程为：
   \(dp[i][j] = \begin{cases} max(dp[i-1][j], dp[i][j-1]) (其他) \\ dp[i-1][j-1] + 1 (s_i = t_j) \end{cases}\)
   其中\(dp[0][j] = 0, dp[i][0] = 0\)，另外可以发现由于\(dp[i-1][j]\)和\(dp[i][j-1]与dp[i-1][j-1]\)最多只差1，所以\(dp[i-1][j-1] + 1 \geq max(dp[i-1][j], dp[i][j-1])\)
   作者比较习惯用下面的方式表达，确实\(+1\)比\(-1\)能给人带来更多的安全感，但以后不再特别说明的话转移方程与下面的等价：
   \(dp[i+1][j+1] = \begin{cases} max(dp[i][j+1], dp[i+1][j]) (其他) \\ dp[i][j] + 1 (s_{i+1} = t_{j+1}) \end{cases}\)
   这个转移方程还是需要一些想象力的，简洁优雅，但是正确性却不是显然的，按自己的经验，当我们得出一个优美的DP方程后，如果想证明它的正确性，往往要从结果出发来倒着想。具体到这个问题，对于任何给定的输入，一定存在一个最长LCS的值，假设为\(k\)，那么这个值一定对应了\(s\)和\(t\)上的\(k\)个不同位置，即：\(s_{p_1}...s_{p_k} = t_{q_1}...t_{q_k}\)，如果\(dp[p_{k-1}][q_{k-1}] = k-1\)，那么按照上述转移方程，也会有\(dp[p_k][q_k] = k\)；一直倒推到起始状态即可
   这样的从结果出发反向思考问题的方法不光有助于证明，有时也有助于得到DP转移方程

2. 完全背包问题
   与“01背包”问题类似，唯一不同的条件是每个物品可以选无限多件，我们还可以按照同样的方式来定义状态：
   \(dp[i][j]\)代表从前\(i\)个物品中取重量不超过\(j\)的物品，答案为\(dp[n][W]\)；
   而决策由原先的取0个还是取1个共2种方式，变为了取0个一直到取k个共k+1种方式：
   \(dp[i][j] = max\{dp[i-1][j-kw_i] + kv_i\}, k \geq 0\)
   状态一共还是\(O(nW)\)种，但每个状态的决策数量(转移方向)由2种变为了k+1种，时间复杂度也升高到了\(O(nkW)\)，其中k最坏可以到达\(W\)，因此最坏时间复杂度为\(O(nW^2)\)
   画出状态转移图后可以发现，\(dp[i][j]\)与\(dp[i][j-w_i]\)的状态转移有着相当大的重合面，当\(dp[i][j]\)采集\(dp[i-1][j-kw_i], k \geq 1\)时(即根据其转移)，\(dp[i][j-w_i]\)采集\(dp[i-1][j-w_i - (k-1)w_i] = dp[i-1][j-kw_i]，k-1 \geq 0\)(对后者而言，这是\(dp[i][j-w_i]\)的所有决策)，一个很自然的想法，如果我们能直接从\(dp[i][j-w_i]\)得出\(dp[i][j]\)就好了
   经过分析可以得出，如果存在一个\(k \geq 1\)可以让\(dp[i][j]\)取得最大值为\(dp[i-1][j-kw_i] + kv_i\)，则\(k-1 \geq 0\)一定能让\(dp[i][j-w_i]\)取得最大值\(dp[i-1][j-w_i - (k-1)w_i] + (k-1)v_i\)，因为如果\(dp[i][j-w_i]\)能取到更大的值，加上\(v_i\)就可以让\(dp[i][j]\)变得更大(这是从实际意义中得出的)，所以当\(k \geq 1\)时，\(dp[i][j]\)的最大值包含在\(dp[i][j-w_i]\)的最大值中，因此我们无需枚举所有的\(k \geq 1\)
   上面的分析需要一些敏锐的观察力，但好歹得到了\(k \geq 1\)时我们可以用1步转移来替代原本的\(O(k)\)步，剩余的决策就只剩下\(k = 0\)了；
   除了上述的分析方法，通过对DP方程变形，也可以得到相同的结果，且数学语言更加严谨：
   \(\begin{align}dp[i][j] &= max\{dp[i-1][j-kw_i] + kv_i\} \\ & = max(dp[i-1][j], max\{dp[i-1][j-kw_i] + kv_i | k \geq 1\}) \\ & = max(dp[i-1][j], max\{dp[i-1][j-(k'+1)w_i] + (k'+1)v_i | k' \geq 0\}) \\ & = max(dp[i-1][j], max\{dp[i-1][j-w_i + kw_i] + kv_i | k \geq 0\} + v_i) \\ & = max(dp[i-1][j], dp[i][j-w_i] + v_i) \end{align}\)
   实际上无限背包在最初我是看别人代码学习的，理解了以后就记住了这个算法，当时我也想了一种证明，现在想来是不完善的，我想办法完善了这个证明，也记录一下。它结合了“归纳法”和“从结果倒推”(即：证明最优结果可被覆盖)，当扩充思路用吧：
   1). 假设\(dp[i-1][j]\)计算出来的都是符合要求的结果；
   2). 如果\(dp[i][j+w_i] = dp[i][j] + v_i\)，则一定会有\(dp[i][j+2w_i] = dp[i][j+w_i] + v_i = dp[i][j] + 2w_i\)，进而有\(dp[i][j+kw_i] = dp[i][j] + kw_i\)；因为\(v_i\)替换掉了原本占用了\(w_i\)重量的从\(1...i-1\)中选取的物品；
   3). 任意由前\(i\)的物品构成的最优解，按照物品种类排序，同一类物品一定相邻；
   4). 对于任何一个最优解\(solve(i, j)\)，按照3)都对应一个按照物品种类排序的序列，我们现在要证明按我们的算法能够取到这个最优解：这个序列如果不包含\(i\)类物品，由于\(dp[i][j]\)继承了\(dp[i-1][j]\)，根据1)，我们能够得到最优解；否则考虑物品序列中第\(i-1\)类物品与第\(i\)类物品的分界线\(j-kw_i\)：\(dp[i][j-kw_i]\)我们由1)得到了最优解，后面都放第\(i\)种物品，因此我们由2)能够计算出最优解；故，对任何最优解\(solve(i, j) = dp[i][j]\)，证毕

3. 01背包问题变型
   与原来的01背包问题相同，但数据范围发生了变化，其中\(1 \leq n \leq 100\)，\(1 \leq w_i \leq 10^7\)，\(1 \leq W \leq 10^9\)，\(1 \leq v_i \leq 100\)
   由于\(W\)规模过大，按原本的方式开不下DP用的数组；但可以注意到\(v_i\)很小，\(\sum v_i \leq 10000\)，因此可以将价值\(v_i\)当作“背包容量”；
   设\(dp[i][j]\)：从前\(i\)件物品中挑选价值为\(j\)的物品，重量的最小值
   \(dp[i][j] = min(dp[i-1][j], dp[i-1][j-v_i] + w_i)\)
   注意原版01背包问题我们求的是重量不超过\(j\)的最大值，“不超过\(j\)”是个范围；而现在我们求的是价值为\(j\)的最小值，“价值为\(j\)”是个精确值；在很多其他DP问题中，定义状态时也需要考虑是使用“不超过\(j\)”、“不小于\(j\)”还是“等于\(j\)”，如果这个维度表示的是一个范围(即“不超过\(j\)”、“不小于\(j\)”)，往往会有简化计算的效果；
   当状态的意义是个精确值“等于\(j\)”，我们又需要一个范围值的时候，可以通过计算前缀的方式求最大最小值来转化为“不超过\(j\)”、“不小于\(j\)”；除此之外，前缀还可以用来计算前缀和，避免当我们需要取一段值的和时遍历所有值
   说回原本的问题，既然\(j\)是个精确值，就有可能不存在任何一种取法使总价值刚好为\(j\)，此时对应的\(dp[i][j]\)就会是一个非法状态，问题的最终答案，我们需要从\(dp[n][j]\)中所有的合法状态找到\(dp[n][j] \leq W\)的最大\(j\)；我们可以记非法的\(dp[i][j] = -1\)，因为没有任何重量会是-1，用它来代表非法值是合适的；由于状态转移是“取最小”，我们也可以用一个足够大的值\(INF\)来代表非法值，这样一个状态不会由非法状态转移过来，除非它的所有决策都转移到了非法状态(即它本身也是一个非法状态)；
   因此有：
   \(\begin{cases} dp[0][0] = 0 \\ dp[0][j] = INF, j \geq 1 \\ dp[i][j] = min(dp[i-1][j], dp[i-1][j-v_i] + w_i), i \geq 1 \end{cases}\)
   在初始状态\(dp[0][j]\)中只有\(dp[0][0] = 0\)：在一个物品都不选的时候唯一的合法价值是0；
   对\(dp[i][j], i \geq 1\)，一定会从\(dp[i-1]\)这层获取到值，因此可以不初始化(但要保证每个值都被计算)；当然由于转移计算是取最小，初始化为\(INF\)也是可以的
   总复杂度为\(O(n\sum V_i)\)，答案为\(max\{j | dp[n][j] \leq W\}\)

4. 多重部分和问题
   有\(n\)种不同大小的数字\(a_i\)，每种数字有\(m_i\)个，是否能从中挑选出若干个数字使其和恰好为\(K\)
   其中\(1 \leq n \leq 100, 1 \leq a_i, m_i \leq 100000, 1 \leq K \leq 100000\)
   这题与“无限背包”有很大的相似性，都是同一种物品有多个的情况，我们可以定义：\(dp[i][j]\)从前\(i\)种数字中挑选出和为\(j\)的可行性，0代表不可行，1代表可行，则有如下转移：
   \(dp[i][j] = max\{dp[i-1][j-ka_i]\}, 0 \leq k \leq m_i\)
   其中\(dp[0][0] = 1，dp[0][j] = 0\)，其他\(dp[i][j], i \geq 1\)为了方便计算可设为0
   我们也可以定义\(dp[i][j]\)从前\(i\)种数字中挑选出和为\(j\)的方案数，则有：
   \(dp[i][j] = \sum dp[i-1][j-ka_i], 0 \leq k \leq m_i\)
   其中\(dp[0][0] = 1，dp[0][j] = 0\)，\(dp[i][j], i \geq 1\)为了累和可设为0
   这里探讨一个问题，有助于在我们初始化整个DP状态时消除疑惑：DP状态应该被初始化为多少？
   以这题为例：\(dp[0][0] = 1，dp[0][j] = 0\)这是由“现实意义”得来的，所以对任何\(dp[0][j], j \geq 0\)而言，它都是有意义的，这是状态转移的基础(base)；而对于任何\(dp[i][j], i \geq 1\)状态，一种情况是他们均会由上一层的合法状态转化而来，例如\(dp[i][j] = max\{dp[i-1][j-ka_i]\}, 0 \leq k \leq m_i\)，\(dp[i][j]\)的值就是上一层若干状态的最大值，它没有所谓“现实意义”下的初始值，我们初始化它为0只是为了方便运算(不影响在迭代过程中不停地做max运算)；而对\(dp[i][j] = \sum dp[i-1][j-ka_i], 0 \leq k \leq m_i\)，\(dp[i][j]\)的值就是上一层若干状态的和，如果我们希望在迭代过程中累计运算这个和，那初始状态自然就要设为0；因此可以看到对于\(j \geq 1\)的状态而言，它们的初始值设为什么，主要是为了保证运算正确，而不是保证现实意义；
   对应的还有另一种情况，即：状态转移的基础(\(dp[0][j]\))中，根据现实意义有无意义的状态(非法状态)；或者状态转移过程中发现某个状态\(dp[i][j] = max\{dp[i-1][j-ka_i]\}, 0 \leq k \leq m_i\)，能够转移到它的上层状态是个“空集”，则这个状态也是无意义的。对于这种会出现无意义状态的状态空间，我们可能会为无意义设定一个值(一般取-1)，并且通过特判断来解决
   继续回到题目本身，按照原先的方式，时间复杂度最差可能会是\(O(nK^2)\)，因此我们还是需要找一下重复状态：
   可以发现\(dp[i][j-a_i]\)与\(dp[i][j]\)有\(m_i\)个状态是重合的(错开了一个\(a_i\)的\(offset\))，我们希望能够从\(dp[i][j-a_i]\)转移到\(dp[i][j]\)，如果\(dp[i][j-a_i] = 0\)，那么所有能转移到\(dp[i][j-a_i]\)的状态都为0，\(dp[i][j]\)就只能指望\(dp[i-1][j]\)了(尽管算法层面意在重复状态简化计算，但是现实意义上仍是多个状态，思维在“算法层面”和“现实层面”转换有帮助更好地理解问题)；
   如果\(dp[i][j-a_i] = 1\)，我们不知道\(dp[i][j-a_i]\)前面用了多少个\(a_i\)转移而来，即不知道\(dp[i][j] = max\{dp[i-1][j-a_i -ka_i]\}\)当中的k是多少。虽然k可能有多个，但如果唯一合法k是\(m_i\)，则我们不能由\(dp[i][j-a_i] = 1\)推导出\(dp[i][j] = 1\)这个结果(因为你不知道它前面用了几个，不知道你的下一步还有没有可用)；
   因此我们需要额外记录当\(dp[i][j]\)合法时，使用了多少个\(a_i\)，并且注意到当存在多个k使得\(dp[i][j] = 1\)时，我们只需要关注最的小k，因为用掉的\(a_i\)越少越好，这样有利于\(dp[i][j]\)向\(dp[i][j+a_i]\)转移；
   故，我们设\(dp[i][j]\)为转移到该状态用掉的最少\(a_i\)，当\(dp[i-1][j]\)有意义，\(dp[i][j] = 0\)；否则\(dp[i][j] = dp[i][j-a_i] + 1, dp[i][j-a_i] \neq -1, dp[i][j-a_i] + 1 \leq m_i\)
   这里需要remind两件事：
   1). 我们在计算\(dp[i][j]\)时只关注\(a_i\)，因为\(a_{i-1}\)及之前的元素在上层已经考虑过了，而我们之所以要关注\(a_i\)是因为它关系到本层的“横向转移”(别忘了记录\(a_i\)最少使用个数的原因，就是为了解决“横向转移”当中的问题)；
   2). “横向转移”可以优化复杂度，但请注意由\(dp[i][j]\)到\(dp[i][j+a_i]\)不仅可以从“现实意义”中理解其合理性，也可以有严谨的证明：“横向转移”本质是状态\(dp[i][j]\)包含着(代表着)与\(dp[i][j+a_i]\)转移状态重合的部分，即如果某个\(k \geq 1\)可以使得\(dp[i][j+a_i]\)从\(dp[i][j+a_i - ka_i]\)合法，它一定可以让\(dp[i][j]\)从\(dp[i][j - (k-1)a_i]\)合法，这两个在同一层\(i\)中的状态之间也有最优子结构性质！(这几乎是个证明了)
   现在给出完整定义和转移方程：
   \(dp[i][j]\)：从前\(i\)种数字中取到和为\(j\)时所使用的最少\(a_i\)个数，当其为-1时代表从前\(i\)种怎么取都无法得到\(j\)这个和
   \(dp[i][j] = \begin{cases} 0, dp[i-1][j] \neq -1 \\ dp[i][j-a_i] + 1, dp[i][j-a_i] \neq -1且dp[i][j-a_i] + 1 \leq m_i \\ -1, 其他 \end{cases}\)
   初始状态\(dp[0][j]\)的值可以设为\(dp[0][0] = 0, dp[0][j] = -1, j \geq 1\)，我们之前说初始这一层是根据实际意义来设置的，当我们改变\(dp[i][j]\)的意义后，第\(0\)层的现实意义就变得很抽象，但还是能知道\(dp[0][0]\)是该层的唯一合法状态，所以其他均为-1，并且它具体值是多少并不影响后续\(dp[i+1][j]\)的计算
   作者用了另一种状态定义：
   \(dp[i+1][j]\)：用前\(i\)种数加和得到\(j\)时最多还能剩余多少个\(a_i\)
   最多还剩下多少，最少使用了多少，逻辑上是等价的：
   \(dp[i+1][j] = \begin{cases} m_i, dp[i][j] \geq 0 \\ dp[i+1][j-a_i] - 1, dp[i+1][j-a_i] \geq 1 \\ -1, 其他 \end{cases}\)
   作者还是从下标0开始的，所以对第一维的理解都是前多少个物品，因此初始状态的定义可以是一致的：\(dp[0][0] = 0, dp[0][j] = -1, j \geq 1\)
   这题给我们的启示是，有一些维度可以记录在值(value)中。

5. 最长上升子序列问题(LIS)
   长为\(n\)的数列\(a_1, a_2, ..., a_n\)，求出最长上升子序列的长度。上升子序列对任意\(i < j\)都有\(a_i < a_j\) (\(n \leq 1000\))
   这题能写出的方程不止一个：
   首先，可以定义\(dp[i]\)代表以\(a_i\)结尾的最长子序列长度，则
   \(dp[i] = max\{1, dp[j]+1|j，初始化状态为\(dp[1] = 1\)；
   由于最优解一定以其中某个元素结尾(这里用到了从结果倒推的思想)，因此答案为\(max\{dp[i] | 1 \leq i \leq n\}\)，时间复杂度为\(O(n^2)\)；
   此外，还可以定义\(dp[i][j]\)：前\(i\)个数中长度为\(j\)的子序列末尾元素的最小值(定义)
   \(dp[i][j] = \begin{cases} min(dp[i-1][j], a_i), j = 1 或 j > 1且a_i > dp[i-1][j-1] \\ dp[i-1][j], 其他 \end{cases}\)
   初始状态\(dp[0][j], j \geq 1\)都不存在(无意义)，由于我们的运算时取最小，并且不会有任何\(a_i > INF\)，因此将无意义的状态设为\(INF\)可以避免特判，方便上述方程的计算；(也可以设\(dp[i][0] = 0\)来避免对\(j = 1\)时的特判)
   最终答案是\(max\{j | dp[n][j] \neq -1\}\)，时间复杂度\(O(n^2)\)；
   由\(dp[i][j]\)的定义可以发现有这样的性质：\(dp[i][j] < dp[i][j+1], dp[i][j] \neq INF, dp[i][j+1] \neq INF\)，即整个\(dp[i]\)数组是单调非减的，值为\(INF\)的元素外的部分是单调递增的；
   因此，对于\(dp[i][j] < a_i\)的状态不能更新，对于\(dp[i][j] \geq a_i\)的状态中只有最左侧的状态可能会发生更新；由于\(dp[i]\)有单调性，因此使用\(lower\_bound\)找到第一个\(\geq a_i\)的位置\(k\)，则一定有\(k=1(对作者的写法来说是0)或dp[i][k] < a_i\)，所以更新\(dp[i][k] = a_i\)即可；
   作者用了一个很巧妙的写法(不禁怀疑是不是以下标为0开始更容易得到优美的实现)：

int dp[MAX_N];

void solve() {
	fill(dp, dp + n, INF);
	for(int i = 0; i < n; i++) {
		*lower_bound(dp, dp + n, a[i]) = a[i]; // 最长的递增子序列长度为$n$，因此这里不会越界
	}
	printf("%d\n", lower_bound(dp, dp + n, INF) - dp); // 下标从0开始，找到对应下标的后一个位置，正好无需+1
}

6. 划分数
   有\(n\)个无区别的物品，将它们划分成不超过\(m\)组，求出划分方法数模\(M\)的余数。其中\(1 \leq m \leq n \leq 1000, 2 \leq M \leq 10000\)
   首先要理清“划分数”的概念，设\(S_k\)代表将\(n\)个无差别物品分为\(k\)组，每组均不为空的方法数，则划分数为\(\sum_{1 \leq k \leq m} S_k\)；其中\((1, 3, 3, 4, 2)\)与\((1, 2, 3, 3, 4)\)算作一种，可看作是按照数量排序后的表示唯一则是同一种划分
   这个问题的解法可以窥探一角算法竞赛究竟可以难到什么程度，曾经武大ACM队长陆神曾经形容说过这比赛是“英语决定下限，数学决定上限”，DP和数学作为算法竞赛中可以出深入内容的领域，竟然还可以结合起来形成组合拳，细思恐极
   题目所求的划分叫做“\(n\)的\(m\)划分”，定义\(dp[i][j]\)为\(i\)的\(j\)划分数，可以发现：
   \(dp[i][j] = \sum dp[i-1][j-k]\)是不对的，因为“第一次取\(x\)个，第二次取\(y\)个”和“第一次取\(y\)个，第二次取\(x\)个”结果上是相同的，产生了重复计数
   正确的方法是，考虑\(n\)的\(m\)划分\(a_i, \sum a_i = n\)，如果对应某类划分对所有\(i\)有\(a_i > 0\)，那么\({a_i}\)对应了\(n-m\)的\(m\)划分；对于另一些划分当中存在\(i\)使得\(a_i = 0\)，这对应了\(n\)的\(m-1\)划分：
   \(dp[i][j] = dp[i-j][j] + dp[i][j-1]\)
   从转移方向上来说\(j\)每次+1，\(i\)有个\(j\)的跨度，为了方便遍历，最好更改定义为：\(dp[i][j]\)为\(j\)的\(i\)划分数，然后有：
   \(dp[i][j] = dp[i-1][j] + dp[i][j-i]\)
   即，按照划分数递增的顺序来DP
   如果\(j < i\)则没有后面那部分，例如\(dp[3][2]\)，根本就不会存在刚才分析的第一种情况：“如果对应某类划分对所有\(i\)有\(a_i > 0\)”(即分类讨论的第一种情况的方法数为0)
   初始状态这边作者没有进行说明，按代码中的设定\(dp[0][0] = 1, dp[0][j] = 0, j \geq 1\)，看似很合理，但是\(dp[0][0] = 1\)这部分就显得有点像哲学问题，但好在我们可以通过小范围的计算“猜”出初始状态：
   \(dp[1][1] = 1\)是显然的，那么按照方程有：
   \(dp[1][1] = dp[0][1] + dp[1][0]\)，由于\(dp[0][j] = 0, j \geq 1\)(将1个物品分为0组事离谱的)，有\(dp[1][0]\) = 1
   \(dp[1][0] = dp[0][0]\)，所以要同时满足\(dp[1][1] = 1\)和递推关系，\(dp[0][0]\)就只能是0

7. 多重集组合数
   (“动态规划”初级篇的守关boss)
   有\(n\)个物品，第\(i\)个物品有\(a_i\)个，相同物品无法区分，问从中取\(m\)个物品共有多少种不同方案，答案对\(M\)取模。\(1 \leq n, m \leq 1000, 1 \leq a_i \leq 1000, 2 \leq M \leq 10000\)
   定义\(dp[i][j]\)为前\(i\)种物品取\(j\)个的不同方案数，则有如下转移：
   \(dp[i][j] = \sum_{k=0}^{min(j, a_i)} dp[i-1][j-k]\)
   直接求解的时间复杂度为\(O(m\sum a_i)\)，最坏估计\(O(nm^2)\)，无法接受，因此需要寻找优化方法：
   1). 首先有一种常用的方法是求前缀和：我们在求得每一层的\(dp[i][j]\)后，计算前缀和\(prefix[i][j] = \sum dp[i][j], j \geq 0\)，有\(prefix[i][j+1] = prefix[i][j] + dp[i][j+1]\)，因此可以在\(O(m)\)内计算出\(prefix[i][j]\)；之后由\(dp[i][j] = \sum dp[i-1][j-k] = \begin{cases}prefix[i-1][j] - prefix[i-1][j-a_i-1], a_i \leq j-1 \\ prefix[i-1][j], a_i > j\end{cases}\)，可将时间复杂度优化到\(O(nm)\)
   2). 另一种是书中的做法，核心思想还是寻找转移状态的重合面；可以发现本层相邻两个状态：\(dp[i][j]\)和\(dp[i][j-1]\)所采集的状态有很大重合面，不同的是\(dp[i][j]\)相比\(dp[i][j-1]\)多累加了一个\(dp[i-1][j]\)，可能少累加了一个\(dp[i-1][j-a_i-1]\)(当\(a_i \leq j-1\)时候)；因此可以直接写出这样的转移方程：
   \(dp[i][j] = \begin{cases}dp[i][j-1] + dp[i-1][j] - dp[j-a_i-1], a_i \leq j-1 \\dp[i][j-1] + dp[i-1][j], a_i \geq j\end{cases}\)
   我们还可以根据DP方程的变形来发现这个结论：
   \(\begin{align}dp[i][j] & = \sum_{k=0}^{min(j, a_i)} dp[i-1][j-k] \\ & = dp[i-1][j + 0] + \sum_{k=1}^{min(j, a_i)} dp[i-1][j-k] \\ & = dp[i-1][j] + \sum_{k'+1=1}^{min(j, a_i)} dp[i-1][j-(k'+1)] \\ & = dp[i-1][j] + \sum_{k'=0}^{min(j-1, a_i-1)} dp[i-1][j-k'-1)] \\ & = dp[i-1][j] + \sum_{k=0}^{min(j-1, a_i-1)} dp[i-1][j-k-1)] + dp[i-1][j-a_i-1] - dp[i-1][j-a_i-1] \\ & = dp[i-1][j] + \sum_{k=0}^{min(j-1, a_i)} dp[i-1][j-1-k)] - dp[i-1][j-a_i-1] \\ & = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-a_i-1] \end{align}\)
   其中第4行到第6行的部分省略了一次分类讨论，默认了\(a_i \leq j-1\)，如果\(a_i \geq j\)，则可以直接从第4行跳到第6行，因为这时候不\(a_i\)多大都取不到；
   这里将\(k=0\)的情况单独提出来并在之后的变形中变换下标的技术叫做“扰动法”，在《具体数学》中有提及，作者将变形过程写得有些过于简单，容易对读者造成困扰
   我们来思考初始状态(即第一层的状态)，有\(dp[0][j] = 0, j \geq 1\)；当\(a_i \geq j\)时，\(k\)可以取到\(a_i\)，此时\(j\)个物品可以全取第\(i\)个，算作一种方案，因此可以设所有\(dp[i][0] = 1\)，即：一个都不取的方法总是只有一种；
   至此，守关boss终于也被解决了(并没有想象中的难)

当我有天也可以迈入final赛场与他们一决高下的时，当我有幸能够进入空气稀薄地带时，我与顶峰的距离，或许只有恐惧。

滚动数组(一种优化技术)

所有的题目和模型都已解决，现在终于可以怀着轻松的心情看一种优化技术了
从本章涉及的所有题目中可以发现，在状态转移的时候，大多只涉及到两层，我们用\(i-1\)层的状态计算出\(i\)层的状态，所以保存\(n\)层所有的状态并不是必须的，我们最少之需要保存2层的状态即可int dp[2][maxm];，计算出下一层状态后，把这个状态拷贝到第一层的数组当中；
事实上可以避开拷贝操作，当计算出当前这层状态后就放在那，然后下一层的状态覆盖掉已经不会再使用的那层，即：用当前这层的状态dp[flag]计算下一层状态dp[flag^1]，计算完成后使用flag ^= 1;；我们也可以把这个写法改为dp[flag], dp[(flag+1)%2]和flag=(flag+1)%2(也可以直接由下标对2取模：dp[i%2], dp[(i+1)%2]，这样不用引入标记)，这就是滚动数组中“滚动”的含义

除滚动数组外，还存在一种只需要在原数组上转移的技术，例如“01背包问题”：
\(dp[i][j] = max(dp[i-1][j-w_i] + v_i, dp[i-1][j])\)
可以发现状态\(dp[i-1][j-w_i]\)和状态\(dp[i-1][j]\)分别位于状态\(dp[i][j]\)上一层的左上方和正上方，因此我们可以：

for(int i = 1; i <= n; i++) {
	for(int j = W; j >= w[i]; j--) {
		dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
	}
}

因为我们用一个数组记录状态，最开始每个状态是上一层的状态，当遍历\(j\)期间，计算过的状态就变成了本层的状态，也就是说在遍历完成前，数组中可能既存在上一层的状态又存在本层状态；
在遍历由于“01背包”这个模型每个状态的计算都是利用上一层的状态，因此必须保证不能由本层状态转移到本层状态；我们只要让\(j\)从大到小(从右往左)遍历，因为每次都是从左侧采集状态，所以计算出的本层状态不会再被用来计算新的本层状态，这样做是OK的；
再来看“无限背包”的模型：
\(dp[i][j] = max(dp[i-1][j], dp[i][j-w_i] + v_i)\)
由于它同时用到了上层状态和本层状态，\(dp[i][j-w_i]\)在它左侧，因此遍历\(j\)的方向可以从左到右：

for(int i = 1; i <= n; i++) {
	for(int j = w[i]; j <= W; j++) {
		dp[i][j] = max(dp[i][j], dp[i][j-w[i]] + v[i]);
	}
}

本层新计算出来的状态可以参与计算本层的另一个状态：当计算dp[i][j]时，dp[i][j-w[i]]已经是本层的状态了；

我们来思考一下能够利用单个数组进行计算的条件有哪些：

1. 如果\(dp[i][j]\)采集的均为上一层的状态\(dp[i-1][k]\)：当所有\(k\)都有\(k \leq j\)，我们让\(j\)从右向左(从大到小)遍历；当所有\(k\)都有\(k \geq j\)，我们让\(j\)从左向右(从小到大)遍历。这样可以保证用到的都是上一层的状态；如果有的\(k < j\)，有的\(k > j\)，这时候无法使用一个数组来计算，移步滚动数组，可以将上层状态和本层状态分开存储
2. 如果\(dp[i][j]\)采集的既有本层状态\(dp[i][j']\)，又有上一层的状态\(dp[i-1][k]\)：如果所有\(j'\)都有\(j' < j\)，并且所有\(k\)都有\(k \geq j\)，需要让\(j\)从左到右(从小到大)遍历；如果所有\(j'\)都有\(j' > j\)，并且所有\(k\)都有\(k \leq j\)，需要让\(j\)从右到左(从大到小)遍历；即本层状态与上层状态分别位于两侧的情况，可以采用这种方法；相反，如果存在需要用到的本层状态和上层状态同时位于左侧或者右侧，则需要引入滚动数组来解决

滚动数组的技术是实现层面的优化，可以大大节约内存，它与状态和转移方式无关，完全是编程层面可以找到的等价实现，因此在思考问题时，需要区分在哪层，考虑内存优化的时候不要将状态转移本身引入，不然会越思考越混乱；

其他技巧

1. memset是按byte初始化数组的函数，但可以使用0和-1对数组进行初始化，将所有的元素变为0和-1，这与二进制有关，-1的二进制是全1表达，因此多个byte和在一起也仍然会被解释为-1
2. upper_bound和lower_bound熟练后会非常方便；例如，求出长度为\(n\)的有序数组中\(k\)的个数：upper_bound(a, a + n, k) - lower_bound(a, a + n, k)
3. fill函数的使用：fill(a, a + n, 0); 终于不用手动写循环啦！
4. 证明正确性的方法：归纳法+从结果倒推法：1). 归纳能从\(d[i-1]\)向第\(dp[i]\)归纳，也能从\(dp[i][j-k]\)向\(dp[i][j]\)归纳；2). 从结果倒推只需要证明最优解的值按照这个方法可以被覆盖，或任何满足条件的解按照这个方法都会被计数
5. 状态不存在(无意义)时，需要给出合适的初始值；初始值的确定可以参考现实意义，但更重要的是方便运算，保证DP的正确性