行业知识
【算法设计与分析】作业2：动态规划
文章目录
- 题目1 最长递增子序列
- 算法1
- 基本思路
- 伪代码
- 代码
- 算法2
- 基本思路
- 伪代码
- 代码
- 算法3
- 基本思路
- 伪代码
- 题目2 蒙德里安的梦想
- 基本思路
- 伪代码
- 题目3(Jon Kleinberg算法设计 习题）
- 第一问
- 第二问
- 基本思路
- 伪代���
题目1 最长递增子序列
-
最长递增⼦序列（LIS）
-
编程实现求解最长递增⼦序列的三种动态规划算法（⼀些细节请参考课件）
1.1 算法1：令 L ( k ) L(k) L(k)表示 s [ 1.. n ] s[1..n] s[1..n]中以 s [ k ] s[k] s[k]结尾的LIS的长度，原问题即求解 max 1 ≤ k ≤ n L ( k ) \max_{1\le k\le n}L(k) max1≤k≤nL(k)
1.2 算法2：令 L ( i , j ) L(i,j) L(i,j)表示 s [ 1.. n ] s[1..n] s[1..n]中每个元素都⼤于 s [ i ] s[i] s[i]的LIS的长度，再令 s [ 0 ] = − ∞ s[0]=-\infty s[0]=−∞，原问题即求
解 L ( 0 , 1 ) L(0,1) L(0,1)
1.3 算法3：构建数组 L L L，令 L ( k ) L(k) L(k)表示 s [ 1.. n ] s[1..n] s[1..n]中⻓度为 k k k且末尾元素最⼩的递增⼦序列的末尾元素，原问题即求解 L L L的长度
-
-
上述算法仅仅求出LIS的长度，请对其改进以求出具体的序列。⾸先给出每种改进算法的基本思路，然后给出伪代码，并分析算法的时空复杂度。
算法1
基本思路
1 建立递归关系
1.1 要求解的子问题：令 L ( k ) L(k) L(k)表示 s [ 1.. n ] s[1..n] s[1..n]中以 s k s_k sk结尾的 L I S LIS LIS的具体序列。
1.2 如何基于子问题求解原问题：根据 L ( i ) ( 1 ≤ i ≤ k − 1 ) L(i) (1\le i \le k-1) L(i)(1≤i≤k−1)，找到某个下标 i i i，这个下标的值 s i s_i si小于 s k s_k sk 且这个下标对应的具体序列 L ( i ) L(i) L(i)的长度最长。
1.3 基本情况：原始算法中当 k = 1 k=1 k=1时， L ( k ) = 1 L(k)=1 L(k)=1。改进算法中同样认定 k = 1 k=1 k=1时 L ( k ) = 1 L(k)=1 L(k)=1且具体序列中只有 s 1 s_1 s1
1.4 递归情况：记原始算法中 L I S LIS LIS长度为 L e n ( k ) Len(k) Len(k)，本改进算法中具体序列为 L ( k ) L(k) L(k)。根据原始算法中的递归关系，找到使得原始算法中递归关系 L e n ( k ) = max { 1 , max 1 ≤ i ≤ k − 1 { L e n ( i ) + 1 ∣ s k > s i } } Len(k)=\max\{1,\max_{1\le i \le k-1}\{Len(i)+1|s_k>s_i\}\} Len(k)=max{1,max1≤i≤k−1{Len(i)+1∣sk>si}}中满足 s k > s i s_k>s_i sk>si的对应下标 i i i。若 L e n ( k ) = 1 Len(k)=1 Len(k)=1，则认为：以 s k s_k sk结尾的 L I S LIS LIS的具体序列有且只有 s k s_k sk一项，即 L ( k ) = [ s k ] L(k)=[s_k] L(k)=[sk]。若 L e n ( k ) ≠ 1 Len(k)\ne 1 Len(k)=1 ，根据 max 1 ≤ i ≤ k − 1 { L e n ( i ) + 1 ∣ s > s i } } \max_{1\le i \le k-1}\{Len(i)+1|s_>s_i\}\} max1≤i≤k−1{Len(i)+1∣s>si}}的计算情况，可找到以 s k s_k sk为结尾的具体序列中的序列前一项 s i s_i si，即： L ( k ) = [ L ( i ) , s k ] L(k)=[L(i),s_k] L(k)=[L(i),sk]
2 自底向上求解
2.1 备忘录形式：开辟一个新的数组 L a s t [ 1.. n ] Last[1..n] Last[1..n]， L a s t k Last_k Lastk表示使得 L e n ( k ) = max { 1 , max 1 ≤ i ≤ k − 1 { L e n ( i ) + 1 ∣ s k > s i } } Len(k)=\max\{1,\max_{1\le i \le k-1}\{Len(i)+1|s_k>s_i\}\} Len(k)=max{1,max1≤i≤k−1{Len(i)+1∣sk>si}}中满足 s k > s i s_k>s_i sk>si的对应下标 i i i，此时记录 L a s t k = i Last_k=i Lastk=i。即： L a s t k Last_k Lastk表示以 k k k为结尾的LIS的具体序列前一项对应的下标值。若 L a s t k = k Last_k=k Lastk=k,则这个序列没有前一项。
2.2 子问题求解顺序：按自底向上，从左至右的顺序遍历 s [ 1.. n ] s[1..n] s[1..n]，求解序列长度 L e n ( k ) Len(k) Len(k)的同时更新对应的 L a s t k Last_k Lastk。在所有 L e n ( k ) Len(k) Len(k)求解完成后，找到 max 1 ≤ k ≤ n L e n ( k ) \max_{1\le k\le n}Len(k) max1≤k≤nLen(k)的对应 k k k，其为具体序列 L ( k ) L(k) L(k)的最后一项。根据 L a s t Last Last数组一步步找到前一项，头插入到 L ( k ) L(k) L(k)中，并使得 k = L a s t k k=Last_k k=Lastk。重复此过程，直到 L a s t i = i Last_i=i Lasti=i对应的 s i s_i si为序列第一项。
2.3 时空复杂度分析：外层循环遍历 s 1.. n s_{1..n} s1..n，需要 O ( n ) O(n) O(n)时间。内层循环遍历 L e n ( 1.. k ) Len(1..k) Len(1..k)，需要 O ( n ) O(n) O(n)时间。一共两层循环，时间复杂度 O ( n 2 ) O(n^2) O(n2)。空间复杂度上，开辟的数组 L a s t Last Last、 L e n Len Len和用于存储最终序列的 L L L都是一维数组，空间复杂度 O ( n ) O(n) O(n)
伪代码
时间复杂度： O ( n 2 ) O(n^2) O(n2)。空间复杂度： O ( n ) O(n) O(n)
代码
int lis_dp1(const vector &s, int n) { vector L(n + 2); for (int i = 1; i for (int j = 1; j n j>n， L e n ( i , j ) = 0 Len(i,j)=0 Len(i,j)=0，此时 L ( i , j ) = ∅ L(i,j)=\emptyset L(i,j)=∅1.4 递归情况：
L e n ( i , j ) = { 0 i f j > n L e n ( i , j + 1 ) i f s i ≥ s j max { L e n ( i , j + 1 ) 1 + L e n ( j , j + 1 ) o t h e r w i s e Len(i,j)=\begin{cases} 0&\mathrm{if}\ j>n\\ Len(i,j+1)&\mathrm{if}\ s_i\ge s_j\\ \max\begin{cases} Len(i,j+1)\\1+Len(j,j+1) \end{cases}&\mathrm{otherwise} \end{cases} Len(i,j)=⎩ ⎨ ⎧0Len(i,j+1)max{Len(i,j+1)1+Len(j,j+1)if j>nif si≥sjotherwise
对于第 i i i个元素，从 L e n ( i , i + 1 ) Len(i,i+1) Len(i,i+1)开始向右查找，找到令 L e n ( i , j ) = = L e n ( i , j + 1 ) + 1 Len(i,j)==Len(i,j+1)+1 Len(i,j)==Len(i,j+1)+1的 j j j，则 L ( i , i + 1 ) L(i,i+1) L(i,i+1)的具体序列不仅包括当前项 s i s_i si，而且下一项就是 s j s_j sj。从 L e n ( 0 , 1 ) Len(0,1) Len(0,1)开始重复这一过程，找到具体序列。
2 自底向上求解
2.1 备忘录形式：改进算法时，不开辟新的数组，只使用 L e n ( i , j ) Len(i,j) Len(i,j)表示 s 1.. n s_{1..n} s1..n中每个元素大于 s i s_i si的 L I S LIS LIS的长度。
2.2 子问题求解顺序：自底向上求解 L e n Len Len数组。在求解 L e n Len Len这个二维数组的过程中，按从右向左、从下至上的顺序遍历。在求解 L e n Len Len数组完成后，令 i = 0 i=0 i=0，从第 0 0 0个元素 s 0 = − ∞ s_0=-\infty s0=−∞开始，使用类似于双指针的算法，遍历 L e n ( i , j ) Len(i,j) Len(i,j)数组的列，找到使得 L e n ( i , j ) = = L e n ( i , j + 1 ) + 1 Len(i,j)==Len(i,j+1)+1 Len(i,j)==Len(i,j+1)+1的对应 j j j，则说明具体序列 L L L中含有 s j s_j sj，将 s j s_j sj加入到具体序列 L L L中。令 i ← j i\gets j i←j，重复上述求解过程：根据 L e n ( i , j ) Len(i,j) Len(i,j)的值不断找到具体序列中的下一个元素，直到数组被遍历到 L e n ( i , j ) = 0 Len(i,j)=0 Len(i,j)=0的位置。
2.3 时空复杂度分析：有 O ( n 2 ) O(n^2) O(n2)个子问题，求解原序列的时间复杂度为 O ( n ) O(n) O(n)。时空复杂度均为 O ( n 2 ) O(n^2) O(n2)。
伪代码
时间复杂度、空间复杂度都是 O ( n 2 ) O(n^2) O(n2)
代码
int lis_dp2(const vector &s, int n) { // insert code here... vector L(n + 2, vector(n + 2, 0)); for (int i = n; i >= 0; i--) { for (int j = n; j >= i; j--) { if (s[i] >= s[j]) { L[i][j] = L[i][j + 1]; } else { L[i][j] = max(L[i][j + 1], 1 + L[j][j + 1]); } } } return L[0][1];}// revised algorithm 2 to compute a LISvector find_lis_dp2(const vector &s, int n) { // insert code here... vector L(n + 2, vector(n + 2, 0)); for (int i = n; i >= 0; i--) { for (int j = n; j >= i; j--) { if (s[i] >= s[j]) { L[i][j] = L[i][j + 1]; } else { L[i][j] = max(L[i][j + 1], 1 + L[j][j + 1]); } } } vector res; int cur = 0; int i = 1; while (L[cur][i] != 0) { int curlen = L[cur][i]; while (i -
