算法设计与分析---动态规划(期末)

标签：问题 -- --- 算法 期末 word1 最优 dp

1.基本要素 

• 最优子结构-->一个问题的解包含子问题的最优解
• 重叠子问题-->子问题被反复计算

2. 动态规划和分治区别

• 两者都是把大问题转换成小问题/子问题来解决，并且当最优子问题组合成最优大问题。
• 区别1：解决问题的类型
• 动态规划主要用于解决优化问题，即寻找满足一定条件的最优解。而分治算法则主要用于解决复杂问题，不仅包括优化问题，还包括决策问题、搜索问题等。
• 区别2：问题分解方式
• 动态规划将问题分解为一系列相互依赖的子问题，并将解决的过程分为多个阶段。而分治算法将问题分解为多个较小的子问题，然后递归地解决这些子问题。
• 区别3：解决子问题的方式
• 动态规划在解决子问题时，会将解存储起来以便后续阶段使用。而分治算法在解决子问题时，通常会直接调用其他函数或算法来解决。
• 区别4：解的组合方式
• 动态规划的解通常需要在后续阶段使用已经得到的子问题解来组合得到原问题的解。而分治算法的解通常是通过递归地解决子问题，然后将子问题的解合并为原问题的解。

3.动态规划和贪心区别

• 相同点：都是一种求解优化问题的优化算法；都要求原问题必须具有最优子结构性质。
• 不同点：最根本的不同点在于贪心算法由局部最优推导全局最优，动态规划从全局最优出发自底向上计算。
• 贪心算法是一种贪心的策略，每一步都采用局部最优的决策，最终得到全局最优解。因此，贪心算法通常解决的是那些具有贪心选择性质的问题，即局部最优解能导致全局最优解的问题。贪心算法不会回溯，每一步的决策是不可撤回的。
• 动态规划则是通过将原问题分解为子问题来求解的。先解决子问题，然后再将子问题的解组合起来，得到原问题的解。与贪心算法不同，动态规划需要回溯子问题的解，以便于确定全局最优解。

4. 单源单汇点(多段图问题，关键路径)

1.多段图问题

求解源点t到汇点t的最短路径。

cost(i,j)-->i阶段的j节点到汇点的最短路径

cost(i,j) = min ( cost(i+1,p) + c(j,p) )

2.关键路径

参考文章(概念)
参考文章(求解过程)

节点就是事件，路径长度就是活动。

• ve(i):事件i最早发生时间
• vl(i):事件i最晚发生时间
• e(i):活动i最早开始时间
• l(i):活动i最晚开始时间
• l(i)-e(i):完成活动i的时间余量

 l(i)-e(i)==0，就是一个关键活动，不存在富余时间。

(为什么事件时发生，而不是开始？因为只有所有指向事件的活动均完成后，这个事件才会发生。比如：事件a是买土豆，事件b是买黄瓜，事件c是凉拌土豆和黄瓜，只有a,c的活动全部完成，c才可以发生)

如何找到e(i)==l(i)的关键活动？

 

现在怎么求出ve(i)和vl(i)?

• ve(i)-->就是源点到i点得最长路径(也就是耗时最长的活动都完成了，那其他活动也都完成了，i发生了) 
• vl(i)-->用前一个节点的最晚发生事件减去活动时间(若有多个前节点，我们要取最小值，都是最晚了，所以一件都不能耽误)
• 汇点的最早发生事件就是其最晚发生时间，可以理解为工期一共就这么长时间。

递推公式：

ve(j) = max( ve(i) + w(i,j) )

vl(i) = min( vl(j) - w(i,j) )

取一个例子来求解。 

	0	1	2	3	4	5	6	7	8
ve(i)	0	2	3	4	5	6	8	8	11
vl(i)	0	5	4	4	6	6	10	8	11

 

所以关键事件是 (0,3,5,7,8)，关键活动是<0,3><3,5><5,7><7,8>，路径长度是11

5.多源多汇点(弗洛伊德算法)

参考文章

1.初始化

2.将所有点依次当作前驱更新距离

递推公式：下标k代表将k节点作为前驱

6.最长公共子序列(LCS)

字符串X和字符串Y的公共最长子序列是什么（序列不要求连续）

1.定义d[ i ][ j ] --> 表示 X 的 i 位和 Y 的 j 位之前的最长公共子序列的长度

2.递推公式 

• 若  X 的 i 位和 Y 的 j 位 相等：d[ i ][ j ] = d[ i-1 ][ j-1 ]+1
• 若  X 的 i 位和 Y 的 j 位 不相等：d[ i ][ j ] = max( d[ i ][ j-1 ] , d[ i-1 ][ j ] )

 3.初始化

可以看出我们值来的方向有上，左上，左，所以我们必须初始化第一行和第一列。因此我们可以把字符串下标从1开始，这样0位置就自动为0，初始化完成。

4.解题：画两张表，一张通过比较大小关系得到数值c(也就d)，另一张记录数值来的方向s(上：2，左上：1，左边：3)，通过这张表得到答案。

eg.求abacbd,baacd的最长公共子序列

写表时，上述递推公式可以看成

• 若两者相等，左上格+1
• 若两者不相等，取左格子和上格子的最大值，若值也是相同的取上格

	0	b	a	a	c	d
0	0	0	0	0	0	0
a	0	0	1	1	1	1
b	0	1	1	1	1	1
a	0	1	2	2	2	2
c	0	1	2	2	3	3
b	0	1	2	2	3	3
d	0	1	2	2	3	4

	0	b	a	a	c	d
0	0	0	0	0	0	0
a	0	2	1	1	3	3
b	0	1	2	2	2	2
a	0	2	1	1	3	3
c	0	2	2	2	1	3
b	0	1	2	2	2	2
d	0	2	2	2	2	1

 c表的最后一个值就是最长公共子序列的长度

s表是记录过程的表，从最后一个值开始回溯，画出方向，左上方方向的末尾就是最长子序列的部分。

所以最后答案是最长子序列长度是4，为aacd

7.最短编辑路径

1.定义d[ i ][ j ] --> 表示以下标i为结尾的字符串word1，和以下标j为结尾的字符串word2，最近编辑距离为d[i][j]。

2.递推公式

• 若word1[ i ]和word1[ j ]相等，d[ i ][ j ] =  d[ i-1 ][ j-1 ]
• 若word1[ i ]和word1[ j ]不相等，可以进行增删改三种操作
  假设对word1进行操作，分别对应
  d[ i ][ j ] =  d[ i ][ j-1 ]+1，d[ i ][ j ] =  d[ i-1 ][ j ]+1，d[ i ][ j ] =  d[ i-1 ][ j-1 ]+1
  
  假设对word2进行操作，分别对应
  d[ i ][ j ] =  d[ i-1 ][ j ]+1，d[ i ][ j ] =  d[ i ][ j-1 ]+1，d[ i ][ j ] =  d[ i-1 ][ j-1 ]+1
• 综上，若word1[ i ]和word1[ j ]不相等，递推式为：
  min{d[ i ][ j ] =  d[ i ][ j-1 ]+1，d[ i ][ j ] =  d[ i-1 ][ j ]+1，d[ i ][ j ] =  d[ i-1 ][ j-1 ]+1}

3.初始化

可以看出我们值来的方向有上，左上，左，所以我们必须初始化第一行和第一列。因此我们可以把字符串下标从1开始。

d[i][0] ：以下标i为结尾的字符串word1，和空字符串word2，最近编辑距离为dp[i][0]。

那么dp[i][0]就应该是i，对word1里的元素全部做删除操作，即：dp[i][0] = i;

同理dp[0][j] = j;

4.解题：

写表时，上述递推公式可以看成：

• 若两者相等，左上格
• 若两者不相等，min{左上格，上格，左格}+1

eg.

A=xyzab   B=axyzc

	i=0	1	2	3	4	5
j=0	0	1	2	3	4	5
1	1	1	2	3	3	4
2	2	1	2	3	4	4
3	3	2	1	2	3	4
4	4	3	2	1	2	3
5	5	4	3	2	2	3

8.求和最大子数组

1.定义

• dp[ i ] --> 以nums[i]为结尾的最长子数组和
• res[i] --> 记录以nums[i]为结尾的最长子数的开头在哪里

2.递推式

• dp[i]=dp[i-1]
• 如果dp[i-1]>0,dp[i]+=dp[i-1],res[i]=res[i-1]

3.初始化

• dp[i]=nums[i]
• res[i]=i 

4.伪代码 

 9. 01 背包问题

1.定义

• f(i,j) --> 从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
• si --> 表示对应于f(j,x)曲线的阶跃点集合，i代表i物品

2.递推式 

• f(i,j) = max( f( i-1,j ) , f( i-1,j-w[i] ) + v[i] )
• si={ (已背重量,现收益) } --> 可以剪枝 -- > 1.超过背包容量 2.有更优解出现了

3.解题 

4.伪代码

 

标签：问题,--,---,算法,期末,word1,最优,dp
From： https://blog.csdn.net/b810411/article/details/139144365