廖予科 liao.yu.ke@gmail.com PPCA 第二讲 廖予科 liao.yu.ke@gmail.com.

Presentation on theme: "廖予科 liao.yu.ke@gmail.com PPCA 第二讲 廖予科 liao.yu.ke@gmail.com."— Presentation transcript:

1 廖予科 liao.yu.ke@gmail.com
PPCA 第二讲 廖予科

2 能使用动态规划的重要特征：（数学归纳法）
由局部推至全局（过程量） 无后效性 要素： 状态 递推式

3 最长公共子序列（LCS） 最长+公共+子序列
子序列：S = a1a2a3...an，我们任取其中的某些字符ai1ai2…aim，要求{ik}递增，则称其为S的一个子序列 （子串！！） 公共子序列:对于两个序列S，T，若一个序列Q同时为S，T的子序列，则称Q为S，T的公共子序列 最长公共子序列：公共子序列中最长的那个

4 EXAMPLE S = 5, 7, 9, 7, 10, 8 T = 5, 7, 7, 10, 8 LCS(S, T) = 5, 7, 7, 10, 8 S = 1, 2, 3, 4, 5 T = 4, 5, 6, 7, 8 LCS(S, T) = 4, 5

5 如何解决？ 对于一个串X，令Xi表示由前i个字符组成的子串 现在考虑Xi, Yj的最长公共子序列LCS(Xi, Yj)
Xi = x1 x2 x3…...xi – 1 xi Yi = y1 y2 y3…...yj – 1 yj LCS(Xi, Yj) = (LCS(Xi – 1, Yj - 1), xi ) xi = yj Longest(LCS(Xi – 1, Yj), LCS(Xi, Yj – 1) otherwise 为什么没有 LCS(Xi – 1)(Y j – 1)？？

6 推广 三个串的LCS长度 求length[a][b][c] =length[a-1][b-1][c-1]+1
if(charA[a]==charB[b]&&charA[a]==charC[c]) =length[a-1][b-1][c-1]+1  if(charA[a]==charB[b]&&charA[a]!= charC[c]) =max(length[a-1][b-1][c], length[a][b][c-1])

7 else =max(length[a-1][b][c] length[a][b-1][c] length[a][b][c-1] length[a-1][b-1][c] length[a-1][b][c-1] length[a][b-1][c-1]) 最长公共上升子序列？？

8 编辑距离 Levenshtein distance 给定两个字符串S，T，提供三种操作 删除一个字符（dota -》 dot）
插入一个字符（ota -》 dota） 将一个字符变为另一个字符（dote -》 dota） 问将S变为T的最少步骤？？ (date -> dat -> dot -> dota) (date -> dote -> dota)

9 令d(i, j)表示将S的前i个字符，T的前j个字符变为相等所需的最少的操作数
= d(i – 1, j - 1) Xi = Tj =min(d(i – 1, j) + 1, d(i, j - 1) + 1, d(i – 1, j - 1) + 1) Xi != Tj

10 树上的动态规划 经典的动态规划 f[i] = f[i - 1] + a f[i][j] = f[i - 1][j - 1] + a
树形动态规划 f[n] = f[n.left] + f[n.right] + a

11 树形DP特征: 求在树上的最优解/安排问题 一般将子树设为状态，进行动态规划 方向一般有两个：根->叶 叶->根
方向一般有两个：根->叶 叶->根 关于树的根：随即选取或枚举 关于建树：一般建成二叉树，如是多叉树则将 其改为二叉树

12 加分二叉树 问题描述： 设有一个n个节点的二叉树tree的中序遍历为 (1,2,3……n)，其中数字为节点的编号。每个节点 有一个分数，记第i个节点的分数为di，tree及他的 每个子树都有一个加分，对任一颗子树的t的加分计 算如下：t的左子树的加分*t的右子树的加分+t的根 的分数，若某个子树为空，规定其加分为1，叶子 的加分就是其本身的分数，试求一颗符合中序遍历 为(1,2,……n)，且加分最高的二叉树tree，并输出 其tree的最高加分。

13 1：5， 2：7，3：1，4：2，5：10 加分：((5*1)+7)*10+2=122 (7+5)*(10+2)+1=145 5*(1*10+2)+7=67

14 Solution 按长度进行一段一段的局部考虑 用数组f[i,j]表示从节点i到节点j所组成的二叉树的最大加分
f[i,j]= f[i,p-1]* f[p+1,j]+ f[p,p]（p: i -> j） p (i -> p - 1) (P + 1 -> j)

15 建树 1、提取特征，构建树 2、左儿子右兄弟转成二叉树 3、构造动态规划

16 选课 给定N门课程及其相应的学分，但课程之间由相应的依赖关系，如A以来于B，则若想选A这门课，则必须同时选A这门课。任一门课A至多只依赖于一门课，但可同时被多门课所依赖，现给定一个M，求选M门课可所能获得的最大学分值。 （hint：d[i][j]表示在以第i个结点为根的树上选择 j个结点获得的最大分数）

17 Thanks for Listening!!!