算法部分
分治策略
思路
- 把规模较大的问题分解为若干个规模较小的子问题， 这些子问题相互独立且与原问题同类； (该子问题的规模减小到一定的程度就可以容易地解决)
- 依次求出这些子问题的解，然后把这些子问题的解组合起来得到原问题的解。由于子问题与原问题是同类的,故分治法可以很自然地应用递归。
对于分治的时间复杂度分析，我们可以写下以下的式子：
假设算法将规模为n的问题分解为个规模为的子问题解决。分解子问题以及合并子问题的解耗费的时间为。
用伪代码写出来就是
几个比较好的例子包括快速排序，归并排序，和矩阵的乘法。
矩阵乘法
直接相乘
时间复杂度直接爆表，假设每做一次标量乘法耗费时间为m，每做一次标量加法耗费时间为a，那么直接相乘算法的时间复杂度为
分块矩阵法(直接应用分治策略)
Strassen算法
小结：什么时候分治
该问题的规模缩小到一定的程度就可以容易地解决；
该问题可以分解为若干个规模较小的同类问题；
利用该问题分解出的子问题的解可以合并为该问题的解；
该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划更为合适。
动态规划 Dynamic Programming
从斐波那契数列的递归计算来看：
但这样效率很低，存在大量的重复计算。
分析时间复杂度得到，近乎于2指数递增了。
考虑借助于变量存储中间计算结果，消除重复计算。伪代码片断如下：
这样一来。
动态规划的实质是分治和消除冗余，是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解以避免计算重复的子问题，来解决最优化问题的算法策略。
基本步骤：
- 找出最优解的性质，并刻划其结构特征。
- 递归地定义最优值。
- 以自底向上的方式计算出最优值。
- 根据计算最优值时得到的信息，构造最优解。
矩阵链相乘
给定n个连乘的矩阵M1·M2 …Mn-1 ·Mn，问：所需要的最小乘法次数(最优值)是多少次？对应此最小乘法次数，矩阵是按照什么结合方式相乘(最优解)的？
- 穷举法
- 找出所有可能的相乘结合方式；
- 计算每种相乘结合方式所需要的乘法次数;
- 求min;
- 动态规划法
其中是维度，如此一来就可以动态规划求解。
伪代码
算法的时间复杂度为
0-1背包问题
给定n个物品{u1,u2,…,un}和一个背包，物品i 的重量为wi，价值为vi，已知背包的承重量为C。问：在不撑破背包的条件下，选择哪些物品装入背包，得到的总价值最大？
之所以称为0-1 背包问题，是因为一个物品要么装入、要么不装入，这两种状态分别用1 和0 表示。
注意到，这问题也可以穷举，但不难想象的是，很复杂，复杂度是。
考虑进行动态规划，设表示从前个物品里放到承重量为的背包里的最大重量（什么Bellman Equation），那么最后的解就是，现在只需要写出动态规划方程
注意到此时的时间复杂度被控制在。
最长公共子序列问题
给定两个定义在字符集∑上的字符串A和B，长度分别为n和m，现在要求它们的最长公共子序列的长度值(最优值)，以及对应的子序列(最优解) 。
一个长度为n的字符串有2^n个子序列，所以穷举法必不可能。考虑动态规划。
- 找出A字符串所有可能的子序列；
- 对于A的每一个子序列， 判断其是否是B的一个子序列,需要的时间为;
- 求max，总的时间为.
不妨设为A的前个里和B的前个的最长公共子序列，那么可以得出以下DP方程：
时间复杂度在。