文章来源: http://thunderfyc.wordpress.com.cn
递归
将问题转为子问题 解决 降低编程复杂度使用
搜索
DFS
每层递归枚举一个选择 然后继续递归 得到所有解
BFS
将队首的节点扩展之后放入队尾 然后继续扩展 直到没有节点为止
Floodfill
要判断一个格点盘上连通的格点标记
从一个格点开始 将其放入队首 扩展周围邻居格点 如果没访问过 放入队尾 然后继续扩展 直到不可扩展为止
搜索优化
Hash判重
判重的时候利用Hash可以O(1)判定是否访问过
搜索顺序
有的时候从小到大 有的时候从大到小 有的时候根据选择评估得到解得可能性
双向BFS
将初始状态扩展 目标状态扩展 两者重合时结束 得到一条路径
分支定界
扩展节点对于超过可行范围的砍掉
随机化
利用随机打乱输入限制 尽可能得到平均效率
生成随机序列
对于P[i] 将P[i+1]到P[n]中随机找一个 和P[i]交换
搜索过程中随机选择
QuickSort随机选择中枢点
文章来源: http://thunderfyc.wordpress.com.cn
DP
把问题分化为子问题之后 取之最优解 从底向上 或用递归从上往下再往上
最优子结构
能从最优的子问题解答中解答主问题
最优子结构的解需要独立 一个问题的解不会影响到另外一个问题
重叠子问题
两个大问题的若干子问题中 有相同的
注意存储子问题的解 以提高效率
重建最优解
在解决子问题的时候 记录取得最优解的选择 可以从根回溯到解
记忆化
从主问题递归子问题 子问题返回的解记忆下来 以后再子问题的时候可以直接调用
既延续从底开始的不需重复计算的优点 也避免了从底开始会进行很多不必要计算的缺点
记忆化搜索
在搜索过程中 记录下子问题的解 然后如果搜索到这一步骤 就直接取得解
DP的一种表现形式
=====================================================================
8皇后
记录覆盖线的编号 斜边按中间为0 两边为正负的方法记录
利用对称性
Castle
已知图上城堡用颜色染色 然后判断有多少城堡 最大城堡多大
Floodfill
8数码
一个9宫格上8个数字 有一个空格 每次可以把一个数字移到空格上 要把它排成预定样子
A* 或者双向BFS
矩阵连乘的计算代价可以用结合律的方法来减小 求最少计算代价 计算代价为乘法的次数
结合的种类数为 Pn = Σ(Pk*P_n-k) P1 = 1
用opt[i][j]表示从i到j的计算代价 opt[i][j] = min{opt[i][k] + opt[k+1][j] + pi-1*pk*pj} p表示列
另外可用s[i][j]表示取得最优解的k
用从底向上的方法计算的话 就是 for l = 2 to n; for i = 1 to n-l+1; j=i+l-1; for k = i to j-1;
l是枚举当前处理的区间长度 i是左端点 j是右端点 k是最优解选择 很显然 opt[i][k] opt[k+1][j]因为区间长度小于opt[i][j] 所以必然已经解出
已知两序列 求最长的公共子序列(不一定连续)
如果xm = yn zk=xm=yn 而且z(1..k-1)是xm-1 ym-1的LCS
如果xm<>yn 如果zk=xm 那么Z是X和Yn-1的LCS 如果zk=yn 那么Z是Xm-1和Yn的LCS
以c[i][j]表示X到第i Y到第j的最长长度 c[i][j] = c[i-1][j-1]+1 [xi=yj] c[i][j] = max{c[i][j-1], c[i-1][j]} [xi <> yj]
可以用b[i][j]表示是从哪个串过来的 回溯的时候 就可以判断是返回b[i][j-1]还是b[i-1][j]还是b[i-1][j-1]
也可以不用b[][]数组 因为c[][]数组的计算规则能够帮助我们决定b 而c可以利用滚动数组 只记录相邻两行即可
Optimal Binary Search Tree
BST中从根到关键字的路径长度为代价 又知每个关键字的访问概率 求使得期望访问代价最小的BST
每一棵最优BST的子树都是最优BST 然后可以知道左子树一定都小于根 一定都小于右子树 那么在一个有序序列中 确定根的位置 就可确定左右子树范围 通过递归到叶子 就可解决问题
opt[i][j]表示有序表i~j形成的树的最小访问代价 w[i][j]表示访问概率之和 opt[i][j] = min{opt[i][k-1]+opt[k+1][j]+w[i][j]}
可用mid[i][j]表示取最优值时的根
mid[i][j]的取值区间为mid[i][j-1]到mid[i+1][j] 利用这个条件(四边形不等式) 可以将复杂度降为O(n^2)
Planning a Company Party
公司的人事结构形成树 派对中 直接上下级关系不能同时参加 每个人有个高兴值 要求列出合法名单使高兴值最大
以opt[i][0/1]表示 以i为根的树的最大高兴值 0为i参加 1为i不参加
opt[i][0] = Σ(max{opt[k][0],opt[k][1]}) k为i的孩子
opt[i][1] = Σ(opt[k][0])
结果为max{opt[1][0], opt[1][1]}
方案不用存 只要从最优值出发 如果为1 则下属均不参加 如果为0 判断下属的0和1哪个大 即可
Edit Distance
已知一个字符串X 要变成字符串Y 操作过程将X从左至右扫描 合法操作有 1继续 2更改当前字符 3删除当前字符 4插入新字符 5交换下两个字符 6结束 每个操作的代价已知 求最少代价方法
用opt[i][j]表示字符串X[1..i]转换到Y[1..j]的最小代价 从opt[i-1][j] opt[i-1][j-1] opt[i][j-1]向后推得 利用oper[i][j]表示用了何种操作
文章来源: http://thunderfyc.wordpress.com.cn
