动态规划(未完成)

动态规划

一. 概述

1.1 什么是动态规划?

动态规划(英语:Dynamic Programming,简称DP)是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。常常适用于有重叠子问题最优子结构(Optimal substructure)性质的问题,动态规划方法所耗时间往往远少于朴素解法。

在20世纪50年代初,由美国数学家贝尔曼(R.Bellman)等人在研究多阶段决策过程的优化问题时,提出了著名的最优化原理,从而创立了动态规划。

动态规划背后的基本思想非常简单。大致上,若要解一个给定问题,我们需要解其不同部分(即子问题),再根据子问题的解以得出原问题的解。

通常许多子问题非常相似,为此动态规划法试图仅仅解决每个子问题一次,从而减少计算量:一旦某个给定子问题的解已经算出,则将其记忆化存储,以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

概念引入

在现实生活中,有一类活动的过程,由于它的特殊性,可将过程分成若干个互相联系的阶段,在它的每一阶段都需要作出决策,从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定,它依赖于当前面临的状态,又影响以后的发展。当各个阶段决策确定后,就组成一个决策序列,因而也就确定了整个过程的一条活动路线.这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程,这种问题称为多阶段决策问题。在多阶段决策问题中,各个阶段采取的决策,一般来说是与时间有关的,决策依赖于当前状态,又随即引起状态的转移,一个决策序列就是在变化的状态中产生出来的,故有“动态”的含义,称这种解决多阶段决策最优化的过程为动态规划方法 [4] 。

基本思想

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解。每一个解都对应于一个值,我们希望找到具有最优值的解。动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样,但它们具有相同的填表格式 [5] 。

基本概念

  • 多阶段决策问题

如果一类活动过程可以分为若干个互相联系的阶段,在每一个阶段都需作出决策(采取措施),一个阶段的决策确定以后,常常影响到下一个阶段的决策,从而就完全确定了一个过程的活动路线,则称它为多阶段决策问题 [6] 。

各个阶段的决策构成一个决策序列,称为一个策略。每一个阶段都有若干个决策可供选择,因而就有许多策略供我们选取,对应于一个策略可以确定活动的效果,这个效果可以用数量来确定。策略不同,效果也不同,多阶段决策问题,就是要在可以选择的那些策略中间,选取一个最优策略,使在预定的标准下达到最好的效果 [6] 。

  • 动态规划问题中的术语

阶段:把所给求解问题的过程恰当地分成若干个相互联系的阶段,以便于求解,过程不同,阶段数就可能不同.描述阶段的变量称为阶段变量。在多数情况下,阶段变量是离散的,用k表示。此外,也有阶段变量是连续的情形。如果过程可以在任何时刻作出决策,且在任意两个不同的时刻之间允许有无穷多个决策时,阶段变量就是连续的 [6] 。

状态:状态表示每个阶段开始面临的自然状况或客观条件,它不以人们的主观意志为转移,也称为不可控因素。在上面的例子中状态就是某阶段的出发位置,它既是该阶段某路的起点,同时又是前一阶段某支路的终点 [6] 。

无后效性:我们要求状态具有下面的性质:如果给定某一阶段的状态,则在这一阶段以后过程的发展不受这阶段以前各段状态的影响,所有各阶段都确定时,整个过程也就确定了。换句话说,过程的每一次实现可以用一个状态序列表示,在前面的例子中每阶段的状态是该线路的始点,确定了这些点的序列,整个线路也就完全确定。从某一阶段以后的线路开始,当这段的始点给定时,不受以前线路(所通过的点)的影响。状态的这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展,这个性质称为无后效性 [6] 。

决策:一个阶段的状态给定以后,从该状态演变到下一阶段某个状态的一种选择(行动)称为决策。在最优控制中,也称为控制。在许多问题中,决策可以自然而然地表示为一个数或一组数。不同的决策对应着不同的数值。描述决策的变量称决策变量,因状态满足无后效性,故在每个阶段选择决策时只需考虑当前的状态而无须考虑过程的历史 [6] 。

决策变量的范围称为允许决策集合 [6] 。

策略:由每个阶段的决策组成的序列称为策略。对于每一个实际的多阶段决策过程,可供选取的策略有一定的范围限制,这个范围称为允许策略集合 [6] 。

允许策略集合中达到最优效果的策略称为最优策略 [6] 。

给定k阶段状态变量x(k)的值后,如果这一阶段的决策变量一经确定,第k+1阶段的状态变量x(k+1)也就完全确定,即x(k+1)的值随x(k)和第k阶段的决策u(k)的值变化而变化,那么可以把这一关系看成(x(k),u(k))与x(k+1)确定的对应关系,用x(k+1)=Tk(x(k),u(k))表示。这是从k阶段到k+1阶段的状态转移规律,称为状态转移方程 [6] 。

最优化原理:作为整个过程的最优策略,它满足:相对前面决策所形成的状态而言,余下的子策略必然构成“最优子策略” [6] 。

最优性原理实际上是要求问题的最优策略的子策略也是最优 [6] 。

基本结构

多阶段决策问题中,各个阶段采取的决策,一般来说是与时间有关的,决策依赖于当前状态,又随即引起状态的转移,一个决策序列就是在变化的状态中产生出来的,故有“动态”的含义,称这种解决多阶段决策最优化问题的方法为动态规划方法 [7] 。

适用条件

任何思想方法都有一定的局限性,超出了特定条件,它就失去了作用。同样,动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性 [8] 。

最优化原理可这样阐述:一个最优化策略具有这样的性质,不论过去状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。简而言之,一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质 [8] 。

将各阶段按照一定的次序排列好之后,对于某个给定的阶段状态,它以前各阶段的状态无法直接影响它未来的决策,而只能通过当前的这个状态。换句话说,每个状态都是过去历史的一个完整总结。这就是无后向性,又称为无后效性 [8] 。

  • 子问题的重叠性

动态规划算法的关键在于解决冗余,这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术,它在实现的过程中,不得不存储产生过程中的各种状态,所以它的空间复杂度要大于其他的算法。选择动态规划算法是因为动态规划算法在空间上可以承受,而搜索算法在时间上却无法承受,所以我们舍空间而取时间

1.2 使用场景

动态规划在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题,它们的结果都逐渐被计算并被保存,从简单的问题直到整个问题都被解决。因此,动态规划保存递归时的结果,因而不会在解决同样的问题时花费时间。

动态规划只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解(对有些问题这个要求并不能完全满足,故有时需要引入一定的近似)。简单地说,问题能够分解成子问题来解决。

适用情况:

  • 最优子结构性质:如果问题的最优解所包含的子问题的解也是最优的,我们就称该问题具有最优子结构性质(即满足最优化原理)。最优子结构性质为动态规划算法解决问题提供了重要线索。

  • 无后效性:即子问题的解一旦确定,就不再改变,不受在这之后、包含它的更大的问题的求解决策影响。

  • 子问题重叠性质:子问题重叠性质是指在用递归算法自顶向下对问题进行求解时,每次产生的子问题并不总是新问题,有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质,对每一个子问题只计算一次,然后将其计算结果保存在一个表格中,当再次需要计算已经计算过的子问题时,只是在表格中简单地查看一下结果,从而获得较高的效率,降低了时间复杂度。

1.3 动态规划与记忆化搜索

https://www.luogu.com.cn/blog/interestingLSY/memdfs-and-dp

二. 算法

2.1 DP的两种实现方式

  • 递归实现
  • 记忆化搜索

2.2 DP常用来解决的问题

  • 切割钢条问题
  • Floyd最短路问题
  • 最大不下降子序列
  • 矩阵链乘
  • 凸多边形三角剖分
  • 0-1背包
  • 最长公共子序列
  • 最优二分搜索树

2.3 使用动态规划的算法

  • 最长公共子序列
  • Floyd-Warshall算法
  • Viterbi算法
  • 求解马可夫决策过程下最佳策略

2.4 实现原理

  • 基本思想:问题的最优解如果可以由子问题的最优解推导得到,则可以先求解子问题的最优解,在构造原问题的最优解;若子问题有较多的重复出现,则可以自底向上从最终子问题向原问题逐步求解。
  • 使用条件:可分为多个相关子问题,子问题的解被重复使用
    • Optimal substructure(优化子结构):
      • 一个问题的优化解包含了子问题的优化解
      • 缩小子问题集合,只需那些优化问题中包含的子问题,降低实现复杂性
      • 我们可以自下而上的
    • Subteties(重叠子问题):在问题的求解过程中,很多子问题的解将被多次使用。
  • 动态规划算法的设计步骤:
    • 分析优化解的结构
    • 递归地定义最优解的代价
    • 自底向上地计算优化解的代价保存之,并获取构造最优解的信息
    • 根据构造最优解的信息构造优化解
  • 动态规划特点:
    • 把原始问题划分成一系列子问题;
    • 求解每个子问题仅一次,并将其结果保存在一个表中,以后用到时直接存取,不重复计算,节省计算时间
    • 自底向上地计算。
    • 整体问题最优解取决于子问题的最优解(状态转移方程)(将子问题称为状态,最终状态的求解归结为其他状态的求解)

三. 算法题

动态规划等价于记忆化搜索,学习深度优先搜索和记忆化搜索,方便快速理解动态规划

解决DP算法问题,写出记忆化搜索的递归函数,列出方程后,可以用数学方法,魔改优化。

3.1 背包问题

背包问题作为NP完全问题,暂时不存在多项式时间算法。动态规划属于背包问题求解最优解的可行方法之一。此外,求解背包问题最优解还有搜索法等,近似解还有贪心法等,分数背包问题有最优贪心解等。 背包问题具有最优子结构和重叠子问题。动态规划一般用于求解背包问题中的整数背包问题(即每种物品所选的个数必须是整数)。

解整数背包问题: 设有n件物品,每件价值记为 Pi ,每件体积记为 Vi ,用一个最大容积为 Vmax 的背包,求装入物品的最大价值。 用一个数组 f[i,v] 表示取i件商品填充一个容积为v的背包的最大价值,显然问题的解就是 f[n,Vmax] 。

{\displaystyle f[i,v]={\begin{cases}f[i-1,v],v<V_{i}\\\max\{f[i-1,v],f[i-1,v-V_{i}]+P_{i}\},v\geq V_{i}\\0,iv=0\\\end{cases}}}

对于特例0-1背包问题(即每件物品最多放1件,否则不放入)的问题,状态转移方程:

{\displaystyle f[i,v]={\begin{cases}f[i-1,v],v<V_{i}\\\max\{f[i-1,v],f[i-1,v-V_{i}]+P_{i}\},v\geq V_{i}\\0,iv=0\\\end{cases}}}

3.2 切割钢条问题

(1)剑指14-剪绳子1

此案例中动态规划效率要低于贪心解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
/**
* 剪绳子1
*
* 给你一根长度为 n 的绳子,请把绳子剪成整数长度的 m 段(m、n都是整数,n>1并且m>1),
* 每段绳子的长度记为 k[0],k[1]...k[m-1] 。
* 请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少?
* 例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。
*
* 示例 1:
*
* 输入: 2
* 输出: 1
* 解释: 2 = 1 + 1, 1 × 1 = 1
* 示例 2:
*
* 输入: 10
* 输出: 36
* 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
* 提示:
*
* 2 <= n <= 58
*
* Related Topics
* 数学
* 动态规划
*/
public class Jz14CuttingRope1 {

public static void main(String[] args) {
System.out.println(cuttingRope(2));
System.out.println(cuttingRope(10));
}

/**
* 求长度为n的绳子剪掉后的最大乘积,可以从前面比n小的绳子转移而来
*
* 用一个dp数组记录从0到n长度的绳子剪掉后的最大乘积,也就是dp[i]表示长度为i的绳子剪成m段后的最大乘积,初始化dp[2] = 1
*
* 我们先把绳子剪掉第一段(长度为j),如果只剪掉长度为1,对最后的乘积无任何增益,所以从长度为2开始剪
*
* 剪了第一段后,剩下(i - j)长度可以剪也可以不剪。
* 如果不剪的话长度乘积即为j * (i - j);
* 如果剪的话长度乘积即为j * dp[i - j]。
* 取两者最大值max(j * (i - j), j * dp[i - j])
*
* 第一段长度j可以取的区间为[2,i),对所有j不同的情况取最大值,因此最终dp[i]的转移方程为
*
* dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]))
*
* 最后返回dp[n]即可
*
* 时间复杂度:O(n ^ 2)
* 空间复杂度:O(n)
*/
public static int cuttingRope(int n) {
int[] dp = new int[n + 1];
dp[2] = 1;
for(int i = 3; i < n + 1; i++){
for(int j = 2; j < i; j++){
dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
}
}
return dp[n];
}

/**
* 贪心
*
* 核心思路是:尽可能把绳子分成长度为3的小段,这样乘积最大
*
* 步骤如下:
*
* 如果 n == 2,返回1,如果 n == 3,返回2,两个可以合并成n小于4的时候返回n - 1
* 如果 n == 4,返回4
* 如果 n > 4,分成尽可能多的长度为3的小段,每次循环长度n减去3,乘积res乘以3;最后返回时乘以小于等于4的最后一小段
* 以上2和3可以合并
*
* 时间复杂度:O(n)
* 空间复杂度:O(1)
*/
public static int cuttingRope1(int n) {
if(n < 4){
return n - 1;
}
int res = 1;
while(n > 4){
res *= 3;
n -= 3;
}
return res * n;
}

}

(2)剑指14-剪绳子2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/**
* 剪绳子2
*
* 给你一根长度为 n 的绳子,请把绳子剪成整数长度的 m 段(m、n都是整数,n>1并且m>1),
* 每段绳子的长度记为 k[0],k[1]...k[m - 1] 。
* 请问 k[0]*k[1]*...*k[m - 1] 可能的最大乘积是多少?
* 例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。
*
* 答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。
*
*
* 示例 1:
*
* 输入: 2
* 输出: 1
* 解释: 2 = 1 + 1, 1 × 1 = 1
* 示例 2:
*
* 输入: 10
* 输出: 36
* 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
*
*
* 提示:
*
* 2 <= n <= 1000
*
* Related Topics
* 数学
* 动态规划
*
* 与剪绳子1唯一不同在于本题目涉及 “大数越界情况下的求余问题”
*
*/
public class Jz14CuttingRope2 {

public static void main(String[] args) {
System.out.println(cuttingRope(2));
System.out.println(cuttingRope(10));
}

public static int cuttingRope(int n) {
if(n < 4){
return n - 1;
}
long res = 1;
while(n > 4){
res = res * 3 % 1000000007;
n -= 3;
}
return (int) (res * n % 1000000007);
}
}

3.3 正则表达式匹配

剑指19-正则表达式匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
/**
* 正则表达式匹配
*
* 请实现一个函数用来匹配包含'. '和'*'的正则表达式。
* 模式中的字符'.'表示任意一个字符,而'*'表示它前面的字符可以出现任意次(含0次)。
* 在本题中,匹配是指字符串的所有字符匹配整个模式。
* 例如,字符串"aaa"与模式"a.a"和"ab*ac*a"匹配,但与"aa.a"和"ab*a"均不匹配。
*
* 示例 1:
*
* 输入:
* s = "aa"
* p = "a"
* 输出: false
* 解释: "a" 无法匹配 "aa" 整个字符串。
* 示例 2:
*
* 输入:
* s = "aa"
* p = "a*"
* 输出: true
* 解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此,字符串 "aa" 可被视为 'a' 重复了一次。
* 示例 3:
*
* 输入:
* s = "ab"
* p = ".*"
* 输出: true
* 解释: ".*" 表示可匹配零个或多个('*')任意字符('.')。
* 示例 4:
*
* 输入:
* s = "aab"
* p = "c*a*b"
* 输出: true
* 解释: 因为 '*' 表示零个或多个,这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
* 示例 5:
*
* 输入:
* s = "mississippi"
* p = "mis*is*p*."
* 输出: false
* s 可能为空,且只包含从 a-z 的小写字母。
* p 可能为空,且只包含从 a-z 的小写字母以及字符 . 和 *,无连续的 '*'。
* 注意:本题与主站 10 题相同:https://leetcode-cn.com/problems/regular-expression-matching/
*
* Related Topics
* 动态规划
*/
public class Jz19IsMatch {

public static void main(String[] args) {
String s = "aa";
String p = "a";
System.out.println(isMatch(s, p));

s = "aa";
p = "a*";
System.out.println(isMatch(s, p));

s = "ab";
p = ".*";
System.out.println(isMatch(s, p));

s = "aab";
p = "c*a*b";
System.out.println(isMatch(s, p));

s = "mississippi";
p = "mis*is*p*.";
System.out.println(isMatch(s, p));
}

/**
* 字符非.或*,则直接比较。
* 字符为.,则直接匹配,跳到下一个字符。
* 字符为*,则找到下一个与其匹配的字符。
*/
public static boolean isMatch(String s, String p) {
int n = s.length();
int m = p.length();
// 存放已处理结果
boolean[][] f = new boolean[n + 1][m + 1];

for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
//分成空正则和非空正则两种
if (j == 0) {
f[i][j] = i == 0;
} else {
//非空正则分为两种情况 * 和 非*
if (p.charAt(j - 1) != '*') {
if (i > 0 && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.')) {
f[i][j] = f[i - 1][j - 1];
}
} else {
//碰到 * 了,分为看和不看两种情况
//不看
if (j >= 2) {
f[i][j] |= f[i][j - 2];
}
//看
if (i >= 1 && j >= 2 && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.')) {
f[i][j] |= f[i - 1][j];
}
}
}
}
}
return f[n][m];
}
}

解题思路:

假设主串为 A,模式串为 B 从最后一步出发,需要关注最后进来的字符。假设 A 的长度为 n ,B 的长度为 m ,关注正则表达式 B 的最后一个字符是谁,它有三种可能,正常字符、*.(点),那针对这三种情况讨论即可,如下:

  1. 如果 B 的最后一个字符是正常字符,那就是看 A[n-1] 是否等于 B[m-1] ,相等则看 A0..n-2 与 B0..m−2 ,不等则是不能匹配,这就是子问题。
  2. 如果 B 的最后一个字符是 . ,它能匹配任意字符,直接看 A0..n-2 与 B0..m−2
  3. 如果 BB 的最后一个字符是 * 它代表 B[m-2]=c 可以重复0次或多次,它们是一个整体 c*
    • 情况一:A[n-1] 是 0 个 c,B 最后两个字符废了,能否匹配取决于 A0..n-1 与 B0..m−3 是否匹配
    • 情况二:A[n-1] 是多个 c 中的最后一个(这种情况必须 A[n-1]=c 或者 c=’.’),所以 A 匹配完往前挪一个,B 继续匹配,因为可以匹配多个,继续看 A0..n-2 与 B0..m−1 是否匹配。

转移方程:

f[i][j] 代表 A 的前 i 个和 B 的前 j 个能否匹配:

  • 对于前面两个情况,可以合并成一种情况 f[i][j] = f[i-1][j-1]
  • 对于第三种情况,对于 c* 分为看和不看两种情况
    • 不看:直接砍掉正则串的后面两个, f[i][j] = f[i][j-2]
    • 看:正则串不动,主串前移一个,f[i][j] = f[i-1][j]

初始条件

特判:需要考虑空串空正则

  • 空串和空正则是匹配的,f[0][0] = true
  • 空串和非空正则,不能直接定义 true 和 false,必须要计算出来。(比如A=’’ ,B=a∗b∗c∗)
  • 非空串和空正则必不匹配,f[1][0] =…= f[n][0] =false
  • 非空串和非空正则,那肯定是需要计算的了。

大体上可以分为空正则和非空正则两种,空正则也是比较好处理的,对非空正则我们肯定需要计算,非空正则的三种情况,前面两种可以合并到一起讨论,第三种情况是单独一种,那么也就是分为当前位置是 * 和不是 * 两种情况了。

复杂度分析

时间复杂度:O(mn),其中 m 和 n 分别是字符串 s 和 p 的长度。我们需要计算出所有的状态,并且每个状态在进行转移时的时间复杂度为 O(1)。

空间复杂度:O(mn),即为存储所有状态使用的空间。

3.4 编号动态规划:最大不下降子序列

  本类的状态是基础的基础,大部分的动态规划都要用到它,成为一个维。

  • 最长不下降子序列定义:从序列中选出若干个数组成一个新的序列,不改变他们的队伍的顺序,要求新的序列里xi≤xi+1≤xi+1…..举个例子{4,6,5,7,3},最长不下降子序列就是{4,6,7}。
  • 子问题的表示:令dp[i]表示以第i个元素结尾的前i个元素构成的最长不下降子序列的长度
  • 优化子结构:若最长不下降子序列包括ak,则必有一个解包含a1,a2…ak-1的最长不下降子序列,dp[i]表示为前i个元素的序列的最长不下降子序列
  • 方程dp[i] = max{dp[j] | 0<j<i , aj≥ai} + 1
  • 伪代码

    输入a[1,…,n]  输出:最长子序列

    img

时间复杂度:O(n^2)

3.5 划分动态规划:矩阵链乘、凸多边形三角剖分

【矩阵链乘】

  • 优化子结构:若计算A1n的优化顺序在k处断开矩阵链, 即A1n=A1k × Ak+1n,则在A1n的优化顺序中,对应于子问题A1k的解必须是A1-k的优化解,对应于子问题Ak+1n的解必须是Ak+1n的优化解
  • 子问题重叠性:

    img

  • 方程:

假设:m[i, j] = 计算Ai~j的最小乘法数; A1 … AkAk+1 …. An 是优化解(k实际上是不可预知)

 img

  img

  • 伪代码:

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
输入:<A1, A2, ..., An>, Ai是矩阵
输出:计算A1 x A2 x ... x An的最小代价方法

Matrix-Chain-Order(p)
n=length(p)-1
FOR i=1 TO n DO
m[i, i]=0;
FOR l=2 TO n DO /* 计算地l对角线*/
FOR i=1 TO n-l+1 DO
j=i+l-1;
m[i, j]= ∞;
FOR k←i To j←1 DO /* 计算m[i,j] */
q=m[i, k]+m[k+1, j]+ pi-1pkpj
IF q<m[i, j] THEN m[i,j]=q; s[i,j]=k;
Return m and s.

复制代码

复制代码

1
2
3
4
5
6
7
Print-Optimal-Parens(s, i, j) //构建最优解,输出A1-n的优化计算顺序
IF j=i
THEN Print “A”i;
ELSE Print “(”
Print-Optimal-Parens(s, i, s[i, j])
Print-Optimal-Parens(s, s[i, j]+1, j)
Print “)”

复制代码

  • 算法复杂度
    • 计算代价的时间:三层循环 O(n3)
    • 构建最优解的时间: O(n)
    • 总时间复杂度:O(n3)
  • 空间复杂度
    • 使用数组m和s
    • 需要空间O(n3)

【三角剖分】

  • 优化子结构:将多边形P划分为不相交三角形的弦的集合
  • 优化问题:

img

  • 方程:设t[i,j] = <vi-1,vi,…..,vj>的优化三角剖分代价

     img

3.6 数轴动态规划:0-1背包

  • 问题描述:给定n种物品和一个背包,物品i的重量是wi,价值vi,背包容量为C,问如何选择装入背包的物品,使装入背包中的物品的总价值最大?对于每种物品总能选择完全装入或不装入,一个物品最多装入一次。
  • 等价整数规划问题:

    img

  • Naive的方法:每个物品只有两种选择:不装或装,n个物品共2n个装取方案,每个装取方案的计算代价为n,总计算代价为O(n2n)

  • 问题的划分:

     img

  • 定义代价矩阵m与方程

    • ***定义m(i, j)* :**背包容量为j,可选物品为xi,xi+1…xn时,问题的最优解代价时m[i,j]
    • m(n, j) = 0, 0j <wn
    • m(n, j) = vn, j ≥**wn
    • m(i, j) = m(i+1, j),    0≤ j< wi
    • m(i, j) = max{m(i+1, j), m(i+1, j-wi)+vi}, j ≥ wi
  • 优化子结构和自底向上的代价

  imgimg

  • 伪代码

复制代码

输入:C>0, wi>0, vi>0, 1≤ i≤n
输出:(x1, x2, …, xn), xi∈{0, 1}, 满足 ∑1≤i≤nwi xi ≤C, ∑1≤i≤nvi xi 最大

1
2
3
4
5
6
7
8
9
10
11
For j=0 To min(wn-1, C) Do
m[n, j] = 0;
For j=wn To C Do
m[n, j] = vn;
For i=n-1 To 2 Do
For j=0 To min(wi -1, C) Do
m[i, j] = m[i+1, j];
For j=wi To C Do
m[i, j]=max{m[i+1, j], m[i+1, j-wi]+vi};
If C<w1 Then m[1, C]=m[2, C];
Else m[1, C]=max{m[2, C], m[2, C-w1]+v1};

复制代码

复制代码

1
2
3
4
5
6
m(1, C)是最优解代价值,相应解计算如下: //构造优化解
If m(1, C) = m(2, C)
Then x1 = 0;
Else x1 = 1;
如果x1=0, 由m(2, C)继续构造最优解;
如果x1=1, 由m(2, C-w1)继续构造最优解.

复制代码

  • 时间复杂度:
    • 计算代价的时间为O(Cn)
    • 构造最优解的时间:O(Cn)
    • 总时间复杂度为:O(Cn)
  • 空间复杂度:
    • 使用数组m,需要空间O(Cn)

3.7 前缀动态规划:最长公共子序列(LCS)

  • 问题描述:Z是序列X与Y的公共子序列如果Z是X的子序列也是Y的子序列。

  • Naive方法:

    • 枚举X的每个子序列Z
    • 检查Z是否为Y的子序列
    • T(n)=O(n2m)
  • 优化子结构:

    • 设X=(x1, …, xm)、Y=(y1, …, yn)是两个序列, LCSXY=(z1, …, zk)是X与Y的LCS,我们有:
    • 如果xm=yn, 则zk=xm=yn, LCSXY = LCSXm-1Yn-1 + <xm=yn>, LCSXm-1Yn-1是Xm-1和Yn-1的LCS.
    • 如果xm≠yn,且zk≠xm,则LCSXY是Xm-1和Y的LCS,即 LCSXY = LCSXm-1Y
    • 如果xm≠yn,且zk≠yn,则LCSXY是X与Yn-1的LCS,即 LCSXY = LCSXYn-1

    img

  • 子问题重叠性

img

  • 方程:

    img

  • 自底向上计算:

    img

  • 伪代码

img

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
输入:X = (x1,x2,...,xm)Y = (y1,y2,...yn)
输出:Z = XY的最长公共子序列

C[0:m,0:n]: C[i,j]XiYjLCS的长度 B[1:m,1:n]:
B[i,j]是指针,指向计算C[i,j]时所选择的子问题的优化解所对应的C表的表项

LCS-length(X, Y)
mlength(X)nlength(Y)
For i0 To m Do C[i,0]0;
For j0 To n Do C[0,j]0;
For i1 To m Do
For j1 To n Do
If xi = yj
Then C[i,j]C[i-1,j-1]+1B[i,j]←“↖”;
Else If C[i-1,j]C[i,j-1] Then
C[i,j]C[i-1,j]; B[i,j]←“↑”;
Else C[i,j]C[i,j-1]; B[i,j]←“←”;
Return C and B.

Print-LCS(B, X, i, j)
IF i=0 or j=0 THEN Return;
IF B[i, j]=“↖”
THEN Print-LCS(B, X, i-1, j-1);
Print xi;
ELSE If B[i, j]=“↑”
THEN Print-LCS(B, X, i-1, j);
ELSE Print-LCS(B, X, i, j-1).

Print-LCS(B, X, length(X), length(Y))
可打印出XYLCS

复制代码

  • 时间复杂度

    • 计算代价的时间:O(mn)
    • 构造最优解的时间:O(m+n)
    • 总时间复杂度为: O(mn)
  • 空间复杂度

    • 使用数组C和B,需要空间O(mn)

3.8 树形动态规划:最优二分搜索树


参考:

🔗 《维基百科-动态规划

🔗 《【算法复习】动态规划

🔗 《如何理解动态规划?