文章来源: http://thunderfyc.wordpress.com.cn/  

IV Advanced Design and Analysis Techniques
  15 Dynamic Programming
    把问题分化为子问题之后 取之最优解 从底向上 或用递归从上往下再往上

    Elements of Dynamic Programming
      Optimal Substructure 最优子结构
        能从最优的子问题解答中解答主问题
        最优子结构的解需要独立 一个问题的解不会影响到另外一个问题

      Overlapping Subproblems 重叠子问题
        两个大问题的若干子问题中 有相同的
        注意存储子问题的解 以提高效率

     Reconstructing an optimal solution 重建最优解
       在解决子问题的时候 记录取得最优解的选择 可以从根回溯到解

     Memoization 记忆化
       从主问题递归子问题 子问题返回的解记忆下来 以后再子问题的时候可以直接调用
       既延续从底开始的不需重复计算的优点 也避免了从底开始会进行很多不必要计算的缺点

    Assembly-line schedulinng
      有两条生产流水线 每条线上有n个工作站 每对工作站功能一样 但用时不一定一样 从某条线到另外一条线 在第i个工作站的转换时间不一样 已知产品在每条生产线投入生产和走出生产线的用时 求最早完工时间
      fi[j]表示通过第i条生产线 第j个工作站后的时间 fi[j] = min{ fi[j-1] + xi[j], fk[j-1] + tk[j-1] + xi[j]} 另外用li[j]表示从那条线来到这个工作站 这样就能返回路径了

    Matrix-chain Multiplication
      矩阵连乘的计算代价可以用结合律的方法来减小 求最少计算代价 计算代价为乘法的次数
      结合的种类数为 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] 所以必然已经解出

    Longest common subsequence
      已知两序列 求最长的公共子序列(不一定连续)
      如果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可以利用滚动数组 只记录相邻两行即可

    Longest Increasing Subsequence
      已知一个序列 求最长上升序列
      用opt[i]表示到第i个元素的序列长度 opt[i+1] = max{opt[k]+1, a[k] < a[i+1]}
      用pre[i]表示从第i个元素推得

      在推opt[i+1]的时候 可以知道 相等长度的LIS的最后一个元素要尽可能小 用f[i]表示 长度为i的IS的最后一个元素最小是多少
      插入一个元素的时候 找到这个f[i]序列中的恰当位置 插入 保持f[]单调增
      最后f的长度就是LIS的长度 但是f数组不是解答

      特别的 如果一个序列的LIS长度为m 则可以划分为m个不上升序列

    LCS & LIS
      LIS转化为LCS
        已知序列为A 另外序列B为序列A顺序排列后的结果 A和B的LCS即为 LIS
      LCS转化为LIS
        序列A为已知序列 另外序列B中包含的序列A元素提取后 作为顺序排列的结果 即存在逻辑上的大小先后关系 对A作LIS (无重复字符)

    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)

    Bitonic Euclidean Traveling-Salesman Problem
      找到一条最短的闭合路径连接所有的点 从最左边的点访问到最右边的点 再回来
      首先从左到右排序 那么b[i][j]表示从第i个点到第1个点再到第j个点的最短路径长度 那么b[i][j] = b[i][j-1]+|Pj-1Pj| [i<j-1] 其最小子问题为b[i-1][i] 用min{b[k][i-1]+|PkPi|}求得
      因为i到1到j的路径上 j-1必然出现在向左或者向右的路径里 如果向右的话可立得 如果向左的话 必然会为求解b[j-1][j]服务 这个时候枚举中间量即可得到b[j-1][j]的解法
      最后结果b[n][n] = b[n-1][n] + |Pn-1Pn|     
      路径记录r[i][j]=j-1 r[i-1][i] = k r[i][j]为从i出发的下一站 递归到r[k][j] 左右大小决定左右走向

    Printing Neatly
      已知n个单词长度 每行的容纳字符量 打印单词 单词之间有一个空格 单词不能破开 求每行最后剩余空格数立方和的最少值(最后一行不计)
      用c[i][j]表示将第i个单词到第j个单词添加到一行中的剩余空格数立方 opt[i]表示从第1个单词添加到第j个单词的最优值
      很显然 opt[i] = min{opt[k] + c[k+1][i]}
      解答方案存储ans[i] 表示添加到第i个单词时上一行的最后一个单词编号

    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]表示用了何种操作

    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哪个大 即可

    Viterbi Algorithm
      声音识别可以用一个有向图表示 一个结点射向另外一个结点的标签为声音x[i][j] 另外还有概率p[i][j] 给出一个声音序列 找到一条路径从某结点开始 使得这条路径的标签形成给出序列 且路径总概率最大 路径总概率为乘积
      opt[i]表示走到第i个结点的最大概率 从opt[pre[i]]获得 ans[i]表示走到第i结点的结点编号

文章来源: http://thunderfyc.wordpress.com.cn/ 

    Moving on a checkerboard
      把棋子从n*n的棋盘 从最下一行走到最上一行 可以直接向上 或者左上 或者右上 每次从x到y 能够收到p[x][y]美元 也可能扣钱 而且有些x到y的移动不允许 找到最下行任何一点到最上行任何一点的路径的最大获得
      opt[i][j]表示到i行j列的最大价值 由opt[i-1][j-1] opt[i-1][j] opt[i-1][j+1]推得 用或者不用pre[i][j]表示由何而来

    Scheduling to maximize profit
      一台机器要处理n个工作 每个工作有耗时和利益 还有截止时间 机器每次只能做一个工作 工作在截止时间之前做完可以得到钱 不可以中断 处理时间是1到n的整数 求最大利益
      按截止时间排序 opt[i][t]表示在时间t处理完工作i 或者不处理工作i的最大利益 用pre[i][t]表示前一个处理的工作
      opt[i][t] = max{opt[k][t-t[k]]+p[k]} pre[i][t] = k

  16 Greedy Algorithms
    Elements of the greedy strategy
      确定最优子结构之后 证明对于某种策略 所做的最优选择是贪心选择 做出贪心选择之后产生的子问题只有一个是需要进一步求解的
      最优子问题的产生不同于DP的多个 而是只有一个 即线性的
      一般来说 每个贪心算法总能找到一个低效的DP算法
      Greedy-choice property
        每次选择都使得当前最优
      Optimal substructure
        问题的最优解由最优的子问题解得到
      Greedy versus Dynamic Programming
        0-1 knapsack problem 一个物品有价值 体积 可以选择放或者不放进包里 求最大价值
        fractional knapsack problem 一个物品有价值 体积 可以选择放0~1的一部分进包里 求最大价值
        0-1 用DP opt[i][j]表示放到体积j 考虑第i个物品时的最大价值
        fractional 用贪心 用价值除以体积作为性价比 从性价比高的开始放 O(nlgn)
        我们可以用O(n)的时间求得性价比序列的中数后 分组为三组 性交比高组的体积和如果大于总体积 递归求这一组 其他忽略 如果小于总体积 如果加上中位数组小于总体积 就全部加入后递归求低性价比组 时间T(n) = T(n/2)+O(n) T(n) = O(n)

    An activity-selection problem
      若干活动 知道起始终了时间 活动不能同时举行 要求满足最多活动的方案
      按结束时间排序
      DP解法 考虑c[i][j]为第i到第j方案的最大满足数 c[i][j] = max{c[i][k]+c[k][j]+1} k为满足能在i结束后开始 在j开始前结束的活动 最后答案为c[0][n+1]
      贪心解法 am为在i结束后开始 在j开始前结束的活动中 结束时间最早的 那么am必为要求的活动 并且i和m中不再有活动
      只需要将有序表访问 如果后一个开始时间在当前确定列表中结束之后 就加入确定列表

    Interval-graph coloring problem
      若干活动 知道起始终了时间 活动不能同时在一个礼堂举行 问最少要多少礼堂
      朴素解法 先确定第一个礼堂最多多少 再确定第二个…
      高效解法 将起始和结束时间排序后 从头扫描 如果一个活动开始 从空闲礼堂里抽一个 如果一个活动结束 将活动礼堂放回空闲礼堂队列首

    Gas Station
      已知沿途加油站 开始为满油 知道能行多少英里 求最少的停留次数
      从开始 尽可能的向远处行驶到加油站

    Maximum Payoff
      已知两个序列AB 最后的利益为 Π(ai^bi) 重新排列AB元素 是利益最大
      降序排列之后 ai^bi*aj^bj >= ai^bj*aj^bi (bi>=bj ai>=aj => ai^(bi-bj)>=aj^(bi-bj) 同时乘以 ai^bj*aj^bj => ai^bi*aj^bj>=aj^bi*ai^bj)

    Huffman codes
      6个字母的编号为000~101 访问概率已知 如何将它们重新编号 使得期望长度更小 如概率为 45 13 12 16 9 5时 一个最优的编码为 0 101 100 111 1101 1100
      用一棵有n个叶子的二叉树来表示编码 向左为0 向右为1 路径标签序列即为编码 很显然 概率最高的长度最短 概率最低的长度最长 将概率最低的两个结点合并成一个新结点 并作为新结点的孩子 新结点概率为其和 继续建树

    Theoretical foundations for greedy methods
      Matroids 矩阵胚
      矩阵胚是有序对(S, l) S为有限非空集合 l为S的子集族 如果B属于l A是B子集 得到A属于l 那么B是遗传的 如果A属于l B属于l A的模小于B 存在B-A的元素使得A∪{x}属于l 那么M满足交换性
      如果图是无向图 那么S为边集 l中元素A是E的子集当且仅当A不是回路 一组边是独立的当且仅当他们构成森林 这个是图的矩阵胚

      Greedy algorithms on a weighted matroid
      就是在矩阵胚中找最大权值的独立子集
      在最小生成树中 我们用w’(e) = w0 - w(e)来表示矩阵胚的权 其独立子集对应生成树 最大独立子集对应最小生成树
      基于矩阵胚的算法 将S按权递减排序 对于S里面的元素 如果当前独立子集并上X依然在l中 那么就加入

    A task-scheduling problem
      一个系统同时只能处理一个任务 每个任务用1个单位时间完成 每一个任务有截止时间 超过截止时间要罚款 求最小罚款方案
      S集合为工作 d为截止时间 w为罚款
      S的独立子集指 存在一个安排 使得子集中的元素不会误期 那么以这些子集构成的集合l和上S就是一个矩阵胚

  17 Amortized Analysis
    Aggregate analysis
      n个操作用时T(n) 均摊操作时间为T(n)/n
    The accounting method
    The potential method

    Making binary search dynamic
      有n个元素 则有1 2 4 8等容量的表 表或为空或为满 使表容量和为n
      查找 每张表都找过去 复杂度 O((lgn)^2)
      插入 生成长度为1的表 然后不停的和当前操作表合并 直到合并后的表长度的表为空 插入 最差情况O(n) 平均情况O(lgn)
      删除 找到最小的满表 最后元素为y 将其替换被删除元素 把最小满表拆分 因为最小 所以之前的都为空 直接复制表即可 最差O(n) 平均O(lgn)

文章来源: http://thunderfyc.wordpress.com.cn/