【算法设计与分析】作业2：动态规划

题目1 最长递增子序列

1. 最长递增⼦序列（LIS）

   1. 编程实现求解最长递增⼦序列的三种动态规划算法（⼀些细节请参考课件）

      1.1 算法1：令$L(k)$表示$s[\mathrm{1..}n]$中以$s[k]$结尾的LIS的长度，原问题即求解${\max }_{1\le k\le n}L(k)$

      1.2 算法2：令$L(i,j)$表示$s[\mathrm{1..}n]$中每个元素都⼤于$s[i]$的LIS的长度，再令$s[0]=-\infty$，原问题即求
      解$L(0,1)$

      1.3 算法3：构建数组$L$，令$L(k)$表示$s[\mathrm{1..}n]$中⻓度为$k$且末尾元素最⼩的递增⼦序列的末尾元素，原问题即求解$L$的长度

2. 上述算法仅仅求出LIS的长度，请对其改进以求出具体的序列。⾸先给出每种改进算法的基本思路，然后给出伪代码，并分析算法的时空复杂度。

算法1

基本思路

1 建立递归关系

1.1 要求解的子问题：令$L(k)$表示$s[\mathrm{1..}n]$中以$s_k$结尾的$LIS$的具体序列。

1.2 如何基于子问题求解原问题：根据$L(i)(1\le i\le k-1)$，找到某个下标$i$，这个下标的值$s_i$小于$s_k$ 且这个下标对应的具体序列$L(i)$的长度最长。

1.3 基本情况：原始算法中当$k=1$时，$L(k)=1$。改进算法中同样认定$k=1$时$L(k)=1$且具体序列中只有$s_1$

1.4 递归情况：记原始算法中$LIS$长度为$Len(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$的对应下标$i$。若$Len(k)=1$，则认为：以$s_k$结尾的$LIS$的具体序列有且只有$s_k$一项，即$L(k)=[s_k]$。若$Len(k)\ne 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_i$，即：$L(k)=[L(i),s_k]$

2 自底向上求解

2.1 备忘录形式：开辟一个新的数组$Last[\mathrm{1..}n]$，$Las{t}_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$的对应下标$i$，此时记录$Las{t}_k=i$。即：$Las{t}_k$表示以$k$为结尾的LIS的具体序列前一项对应的下标值。若$Las{t}_k=k$,则这个序列没有前一项。

2.2 子问题求解顺序：按自底向上，从左至右的顺序遍历$s[\mathrm{1..}n]$，求解序列长度$Len(k)$的同时更新对应的$Las{t}_k$。在所有$Len(k)$求解完成后，找到${\max }_{1\le k\le n}Len(k)$的对应$k$，其为具体序列$L(k)$的最后一项。根据$Last$数组一步步找到前一项，头插入到$L(k)$中，并使得$k=Las{t}_k$。重复此过程，直到$Las{t}_i=i$对应的$s_i$为序列第一项。

2.3 时空复杂度分析：外层循环遍历$s_{\mathrm{1..}n}$，需要$O(n)$时间。内层循环遍历$Len(\mathrm{1..}k)$，需要$O(n)$时间。一共两层循环，时间复杂度$O(n^2)$。空间复杂度上，开辟的数组$Last$、$Len$和用于存储最终序列的$L$都是一维数组，空间复杂度$O(n)$

伪代码

时间复杂度：$O(n^2)$。空间复杂度：$O(n)$

代码

int lis_dp1(const vector<int> &s, int n) {
    vector<int> L(n + 2);
    for (int i = 1; i <= n; i++) 
        L[i] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            if (s[i] > s[j])
                L[i] = max(L[i], L[j] + 1);
        }
    }
    int res = 0;
    for (int i = 1; i <= n; i++)
        res = max(res, L[i]);
    return res;
}

vector<int> find_lis_dp1(const vector<int> &s, int n) {
    vector<int> L(n + 2);
    vector<int> last(n + 2);
    for (int i = 1; i <= n; i++) {
        L[i] = 1;
        last[i] = i;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            if (s[i] > s[j]) {
                if (L[j] + 1 > L[i]) {
                    L[i] = L[j] + 1;
                    last[i] = j;
                }
            }
        }
    }
    int residx = 0;
    int res = 0;
    for (int i = 1; i <= n; i++) {
        if (L[i] > res) {
            res = L[i];
            residx = i;
        }
    }
    vector<int> resvec;
    int i = residx;
    while (i != last[i]) {
        resvec.insert(resvec.begin(), s[i]);
        i = last[i];
    }
    resvec.insert(resvec.begin(), s[i]);
    return resvec;
}

算法2

基本思路

1 建立递归关系

1.1 要求解的子问题：$Len(i,j)$表示$s_{j..n}$中每个元素都大于$s_i$的$LIS$的长度。令$L(i,j)$表示$s_{j..n}$中每个元素都大于$s_i$的具体序列。

1.2 如何基于子问题求解原问题：令$s_0=-\infty$，原问题即求解$Len(0,1)$的值和$L(0,1)$的具体序列。

1.3 基本情况：若$j>n$，$Len(i,j)=0$，此时$L(i,j)=\varnothing$

1.4 递归情况：
$$Len(i,j)=\{\begin{array}{ll}0& \mathrm{if}j>n\\ Len(i,j+1)& \mathrm{if}{s}_i\ge s_j\\ \max \{\begin{array}{l}Len(i,j+1)\\ 1+Len(j,j+1)\end{array}& \mathrm{otherwise}\end{array}$$
对于第$i$个元素，从$Len(i,i+1)$开始向右查找，找到令$Len(i,j)==Len(i,j+1)+1$的$j$，则$L(i,i+1)$的具体序列不仅包括当前项$s_i$，而且下一项就是$s_j$。从$Len(0,1)$开始重复这一过程，找到具体序列。

2 自底向上求解

2.1 备忘录形式：改进算法时，不开辟新的数组，只使用$Len(i,j)$表示$s_{\mathrm{1..}n}$中每个元素大于$s_i$的$LIS$的长度。

2.2 子问题求解顺序：自底向上求解$Len$数组。在求解$Len$这个二维数组的过程中，按从右向左、从下至上的顺序遍历。在求解$Len$数组完成后，令$i=0$，从第$0$个元素$s_0=-\infty$开始，使用类似于双指针的算法，遍历$Len(i,j)$数组的列，找到使得$Len(i,j)==Len(i,j+1)+1$的对应$j$，则说明具体序列$L$中含有$s_j$，将$s_j$加入到具体序列$L$中。令$i\leftarrow j$，重复上述求解过程：根据$Len(i,j)$的值不断找到具体序列中的下一个元素，直到数组被遍历到$Len(i,j)=0$的位置。

2.3 时空复杂度分析：有$O(n^2)$个子问题，求解原序列的时间复杂度为$O(n)$。时空复杂度均为$O(n^2)$。

伪代码

时间复杂度、空间复杂度都是$O(n^2)$

代码

int lis_dp2(const vector<int> &s, int n) {
   // insert code here...
   vector<vector<int>> L(n + 2, vector<int>(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 LIS
vector<int> find_lis_dp2(const vector<int> &s, int n) {
   // insert code here...
   vector<vector<int>> L(n + 2, vector<int>(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<int> res;
   int cur = 0;
   int i = 1;
   while (L[cur][i] != 0) {
       int curlen = L[cur][i];
       while (i <= n && curlen == L[cur][i]) 
           i++;
       i--;
       res.push_back(s[i]);
       cur = i;
   }
   return res;
}

算法3

基本思路

1.建立递归关系

1.1 要求解的子问题：令$L(k)$表示$s_{\mathrm{1..}n}$中长度为$k$且末尾元素最小的递增子序列的。$L(k).last$表示该序列最后的元素。

1.2 如何基于子问题求解原问题：因为$L(1).last<L(2).last<...<L(k).last$，所以对于长度小于$n$的序列，可以计算所有的$L(k)$的具体序列，并存储。

1.3 基本情况：对于长度为1的序列，$L(1)=[s_1]$

1.4 递归情况:
从左至右遍历原序列$s_{\mathrm{1..}n}$，对于当前元素$s_i$,在$L(k).last$构成的有序数组中使用二分法查找插入位置$k^{\prime }$。若$k^{\prime }$在$L(k).last$数组最后，则$L(k+1)=[L(k),s_i]$,且$L(k+1).last\leftarrow s_i$。否则，$L(k^{\prime }).last\leftarrow s_i$，但原具体序列$L(k)$不变。

2.自底向上求解

2.1 备忘录形式：开辟一个数组$Lidx$，表示序列$L$内各个元素的下标。开辟一个数组$prev$，$pre{v}_i=j$表示：原序列第$i$个元素$s_i$若在最终的具体序列中，则其上一项的下标是$j$，即其上一项$s_j$也在具体序列中。通过$prev$这个备忘录，找到每个元素的前置元素。存储具体序列的最后一项元素$i_{begin}$。用res存储最终的具体序列。

2.2 子问题求解顺序：在原算法中，按自底向上的顺序，在更新$L$数组的同时，更新对应的$Lidx$和$prev$数组。在将$L$求解完成后，求解原序列：根据LIS具体序列中最后一项的下标$i_{begin}$，得知具体序列最后一项含$s_i$，根据$pre{v}_i$，得知具体序列中$s_i$的上一项为$s_{pre{v}_i}$，并令$i=pre{v}_i$。以此种方式循环，直到$i=pre{v}_i$时的$s_i$为序列第一项。

2.3 时空复杂度分析：完整遍历数组需要$O(n)$的时间复杂度，每次遍历时查找并修改需要$O(\log n)$的时间复杂度。总时间复杂度为$O(n\log n)$。需要开辟多个长度为$n$的一维数组，总空间复杂度为$O(n)$

伪代码

时间复杂度$O(n\log n)$,空间复杂度$O(n)$

题目2 蒙德里安的梦想

给定⼀个$3\times n$的棋盘， 设计⼀个动态规划算法计算有多少种使⽤$1\times 2$的骨牌进行完美覆盖的⽅案。完美覆盖是指没有未覆盖的⽅格，也没有堆叠或者悬挂在棋盘外的⻣牌。

基本思路

1.建立递归关系

1.1 要求解的子问题：令$f(i,j)$表示前$i-1$列的骨牌已经放置好，且从第$i-1$列伸出到第$i$列的状态是$j$的所有方案数。记$f(n,0)$为最终的解。

1.2 如何基于子问题求解原问题：在所有横着的小骨牌被放置完成后，只要纵向有两个连续的空格，则可以在纵向的两个连续空格中放置骨牌。所以，记：在某一列中，纵向有0个或2个（偶数个）连续空格的所有骨牌覆盖状态为“有效状态”。将“有效状态”记录进数组$st$中。基于上一列的状态，横放新的小骨牌，就可以转移进入到下一列的状态。在转移时，当前列与下一列不能发生冲突。也需要判断放置后是否会进入无效状态。

如图所示，以红色表示没有被覆盖的块，以黄色表示上一列第$i-1$列中已经被覆盖有骨牌的块。各个原状态在图中最左侧一列。各个状态能转移进入的下一有效状态在图右侧。通过横放新的骨牌，才能转移进入下一状态。新放的骨牌以绿色表示。

在有效状态中，存在偶数个（包括0）个连续的未被覆盖的块，可以竖向放置骨牌。因此，所有能横向放置骨牌的方案数即为总方案数。在最后一列需要读取各个有效状态的方案数。但是，计算中间列$i(1<i<n)$的过程中，中间列$i$不一定是有效状态。

1.3 基本情况：
不放置任何骨牌时，$f_{0,0}=1$

1.4 递归情况:
在第$i$列，遍历所有状态$j$。考虑所有与$j$不冲突且有效的状态$k$，则$f(i,j)={\sum }_{k}f(i-1,k)$

2.自底向上求解

2.1 备忘录形式：$f$是一个二维数组。在$f(i,j)$中，$j$是一个二进制数，由于棋盘行数为3，所以 j ∈ { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 } j\in \{0,1,2,3,4,5,6,7\} j∈{0,1,2,3,4,5,6,7}。根据二进制的位，位为0表示当前位没有被覆盖方块，位为1表示当前位被覆盖方块。在基于子问题求解原问题时，判断当前列状态$x$与下一列状态$y$是否在横行产生冲突，只需要通过位运算$x\&y$，$x\&y=0$的情况表示没有冲突，可以转移。提前预处理“有效状态”进入数组$st$中，$s{t}_j=1$表示$j$状态有效。有效状态中的纵向存在0个或2个连续空格。通过$s{t}_{x|y}$读取$x$状态转换到$y$状态时是否会导致出现没有偶数个连续空格的无效状态情况。

2.2 子问题求解顺序：以自底向上的顺序，从左至右以$i$增长的方式遍历$f(i,j)$。

2.3 时空复杂度分析：内层循环中，状态数$2^3=8$为常数。外层循环中，遍历$f(i,j)$第一维的时间复杂度为$O(n)$。则总体时间复杂度为$O(n)$。虽然$f(i,j)$是一个二维数组，但是第二维状态数只有$2^3=8$是常数。所以总体空间复杂度为$O(n)$

伪代码

题目3(Jon Kleinberg算法设计 习题）

We are given a checkerboard which has 4 rows and columns, and has an integer written in each square. We are also given a set of $2n$ pebbles, and we want to place some or all of these on the checkerboard (each pebble can be placed on exactly one square) so as to maximize the sum of the integers in the squares that are covered by pebbles. There is one constraint: for a placement of pebbles to be legal, no two of them can be on horizontally or vertically adjacent squares (diagonal adjacency is fine).
给定一个有4行、$n$列的棋盘，每个棋盘格中有一个数。给定$2n$个鹅卵石，我们想放置部分或所有鹅卵石到棋盘中，每个鹅卵石都只能覆盖一个格子，将覆盖住的数的总和最大化。只有一个限制：在合法的放置中，没有两个格子在水平或垂直方向相邻。对角线方向相邻是合法的。

第一问

1.1. Determine the number of legal patterns that can occur in any column (in isolation, ignoring the pebbles in adjacent columns) and describe these patterns.
决定合法的放置模式数量，可以出现在任意一列中。（孤立的，忽略相邻列的鹅卵石）。描述这些模式。
记行下标从0开始。
什么都不放置。
只放置第0行。
只放置第1行。
只放置第2行。
只放置第3行。
放置第0行和第2行。
放置第0行和第3行。
放置第1行和第3行。
若使用二进制进行描述，某一位为0表示不放置，某一位为1表示放置，则合法的放置有：0、1、2、4、5、8、9、10。一共有8种模式。
合法的放置模式数量共有8种。

第二问

Call two patterns compatible if they can be placed on adjacent columns to form a legal placement. Let us consider subproblems consisting of the first $k$columns ($1\le k\le n)$. Each subproblem can be assigned a type, which is the pattern occurring in the last column.
Using the notions of compatibility and type, give an $O(n)$-time dynamic programming algorithm for computing an optimal placement.
如果两个模式能放在相邻列，则把两个模式称作“兼容”。考虑子问题只包括前$k$列$(1\le k\le n)$。每个子问题都被赋予一个类型，即最后一列的模式。
根据类型之间的兼容性，给出一个$O(n)$的动态规划算法用于计算最优解。

基本思路

1.建立递归关系
1.1 要求解的子问题：前$i$列$(1\le i\le n)$，其中第$i$列的摆放方案是$j$，得到的最优摆放方案的值，记结果为$f(j,i)$

1.2 如何基于子问题求解原问题：对于第$i$列的方案$j$，遍历所有与$j$方案兼容的方案$k$。$j$和$k$都是二进制编码，某一位为1表示当前位被覆盖，通过所有$f(k,i-1)$的值，加上当前列覆盖住的值，得到当前列的值$f(j,i)$

模式的自兼容情况可以通过位运算得到。模式间的兼容情况也可以通过位运算、两两遍历所有自兼容的模式得到。

0模式兼容0、1、2、4、5、8、9、10模式

1模式兼容0、2、4、8、10模式

2模式兼容0、1、4、5、8、9模式

4模式兼容0、1、2、8、9、10模式

5模式兼容0、2、8、10模式

8模式兼容0、1、2、4、5模式

9模式兼容0、2、4模式

10模式兼容0、1、4、5模式

1.3 基本情况：在第0列，$i=0$,不覆盖任何鹅卵石时，方案的二进制编码$j=0$，$f(0,0)=0$

1.4 递归情况:记当前列在$k$方案下覆盖住的值为$sum$，则对于所有与$k$兼容的$j$,有$f(j,i)=\max (sum+f(k,i-1))$

2.自底向上求解

2.1 备忘录形式：用数组$f(j,i)$表示第$i$列$j$模式下取得的最大值。用数组$p$记录列内自兼容的模式的序号。用数组$compatible$记录每个模式能兼容的模式的序号。用数组$sum(j,i)$表示$j$模式下$i$列的值。

2.2 子问题求解顺序：以自底向上的顺序，根据$f(j,i-1)$求解$f(j,i)$

2.3 时空复杂度分析：时间复杂度：外层循环遍历每一列，$O(n)$。内层循环遍历每种情况。但最多存在8种列内自兼容的情况，列间兼容情况也最多不超过8种。所以总体时间复杂度是$O(n)$。空间复杂度：需要一个行数为8，列数为$n$的二维数组，空间复杂度为$O(n)$

伪代码

文章来源地址https://www.toymoban.com/news/detail-833242.html

到了这里，关于【算法设计与分析】作业2：动态规划的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！