CS 170 2023年秋季 作业7：动态规划

本题无需解答，学生应据实填写本人与组员的姓名及 SID；若独自完成则填写 "none"。

Main Idea: 定义子问题如下：令 \(A[i]\) 为一个布尔变量，表示前缀 \(s[: i]\) 能否被表示成若干编码的连接。我们可以用以下递推关系，借助 \(j < i\) 的 \(A[j]\) 来计算 \(A[i]\)：

\[ A[i] = \bigvee_{\substack{a \in d \\ s[i-\operatorname{length}(d[a])+1:i] = d[a]}} A[i - \operatorname{length}(d[a])] \]

这里规定 \(A[0] = \text{TRUE}\)。算法直接按上述公式计算即可。

Pseudocode:

procedure Translate(s):
    Create an array A of length n + 1 and initialize all entries to FALSE.
    Let A[0] = TRUE
    for i := 1 to n do
        for each symbol a in d do
            if i ≥ length(d[a]) and d[a] = s[i − length(d[a]) + 1 : i] then
                A[i] = A[i] ∨ A[i − length(d[a])]
    return A[n]

Proof of Correctness: 用简单归纳法证明。

基础情况：当 \(i = 0\) 时，\(s[: 0]\) 就是空串，可以被解释为空符号序列，故 \(A[0] = \text{TRUE}\)。

归纳步骤：设 \(A[0], \ldots, A[i - 1]\) 都已取到正确值，证明递推给出 \(A[i]\) 的正确值。我们把 \(s[: i]\) 的所有解释 \(a_1 \ldots a_k\) 按最后一个符号 \(a_k\) 分类。对于 \(a_k = a\)，若 \(s[: i]\) 的后缀与 \(d[a]\) 吻合，则每个解释 \(a_1 \ldots a_k\) 与 \(s[: i - \operatorname{length}(d[a])]\) 的一个解释 \(a_1 \ldots a_{k-1}\) 一一对应；由归纳假设，\(A[i - \operatorname{length}(d[a])]\) 已正确告诉我们 \(s[: i - \operatorname{length}(d[a])]\) 是否可解释。若后缀与 \(d[a]\) 不同，则不存在以 \(a\) 结尾的解释。对所有符号 \(a\) 取逻辑或（\(\lor\)），递推就给出了 \(A[i]\) 的正确值。

程序正是实现了该递推，故输出 \(A[n]\)，即 \(s\) 是否可解释。

Runtime Analysis: 外层 for 循环 \(n\) 次，内层 for 循环 \(k\) 次。每次循环内比较两个字符串是否相等耗时 \(O(\operatorname{length}(d[a])) \leq O(\ell)\)。故总运行时间为 \(O(nk\ell)\)。

（注意：若改用字典树（trie）而非每次重新构造字符串，可把运行时间提升到 \(O((n + k)\)ℓ))，但获满分并不要求这一点。）

Space Complexity Analysis: 我们存储了 \(n\) 个子问题 \(A[\cdot]\)，每个子问题占用常数空间，故整体空间复杂度为 \(O(n)\)。

（注意：由于任意 \(A[i]\) 只依赖于前 \(\ell\) 个子问题，空间可进一步优化到 \(O(\ell)\)。）

算法：在 DAG 上按顶点逆拓扑序进行动态规划。

对每个顶点 \(v\) 计算 \(dp[v]\)，表示一个二元组，包含 \(v\) 的理想目标及其分数。例如若 \(x\) 是 \(v\) 的理想目标，则 \(dp[v] = (x, s[x])\)。

递推更新如下：

\[ dp[v] = \max_{(v,u) \in E} dp[u]\tag{1} \]

随后再令 \(dp[v] = \max(dp[v], (v, s[v]))\)。这里所有的 \(\max\) 都按 \(dp[\cdot]\) 二元组的第二个分量（分数）取。

由于该算法对每个顶点和每条边都只访问常数次，整体运行时间为 \(O(|V| + |E|)\)。

(a) 我们有：

• \(f(1, m) = 1\)，因为只需从那唯一的一层楼扔一次鸡蛋，就能判断它在该层是否会碎。

• \(f(0, m) = 0\)，因为 \(\ell\) 只有一个可能的值。

• \(f(n, 1) = n\)，因为只有一枚鸡蛋，唯一策略是从第 1 层开始逐层向上扔，直到它碎为止。

• \(f(n, 0) = \infty\)（当 \(n > 0\) 时），因为没有鸡蛋可扔，问题不可解。

(b) 若鸡蛋碎了，则只需考虑第 1 到 \(x - 1\) 层，且由于碎了一枚鸡蛋，剩余 \(m - 1\) 枚，此时还需要 \(f(x - 1, m - 1)\) 次投掷。若鸡蛋没碎，则只需考虑第 \(x + 1\) 到 \(n\) 层，且仍有 \(m\) 枚鸡蛋，此时还需要 \(f(n - x, m)\) 次投掷。

(c) 递推关系为

\[ f(n, m) = 1 + \min_{x \in \{1, \ldots, n\}} \max\{f(x - 1, m - 1),\ f(n - x, m)\} \]

当在第 \(x\) 层扔鸡蛋时，最坏情况下需要 \(\max\{f(x - 1, m - 1), f(n - x, m)\}\) 次投掷；最优策略会从 \(n\) 层楼中选择最好的一层，因此还需要 \(\min_{x\in\{1\ldots n\}} \max\{f(x - 1, m - 1), f(n - x, m)\}\) 次投掷。

(d) 按 \(m\)、\(n\) 的递增顺序求解子问题，即：

for j in range(m+1):
    for i in range(n+1):
        solve f(i, j)

(e) 共有 \(nm\) 个子问题，每个子问题耗时 \(O(n)\)，故整体运行时间为 \(O(n^2 m)\)。

(f) 唯一需要存储的是 DP 数组 \(f\)，它包含 \(nm\) 个元素。故整体空间复杂度为 \(O(nm)\)。

(g) 可以！注意在 (c) 的递推中，我们只用到了 \(f(\cdot, m)\) 与 \(f(\cdot, m - 1)\) 的值。因此只需保存目前已计算出的最后两「列」。伪代码如下：

def eggdrop(n, m):
    if m == 0:          # m = 0 的边界
        return float("inf")
    if n == 0:
        return 0
    curr = [i for i in range(n+1)]   # m = 1 的边界
    for j in range(2, m+1):
        prev = copy(curr)
        for i in range(j+1):
            curr[i] = i
        for i in range(j+1, n+1):
            curr[i] = 1 + min([
                max(prev[x-1], curr[i-x])
                for x in range(1, i+1)
            ])
    return curr[n]

(a) 子问题定义：定义 \(B[i_1, j_1, i_2, j_2]\) 为将子矩阵 \(A[i_1 \ldots i_2, j_1 \ldots j_2]\) 分离成「全为咬破块」或「全为干净块」所需的最少切割数。

(b) 递推关系：

\[ B[i_1, j_1, i_2, j_2] = \min \begin{cases} 0, & \text{若 } A[i_1 \ldots i_2,\, j_1 \ldots j_2] \text{ 的所有元素相等} \\ 1 + B[i_1, j_1, i_1 + k, j_2] + B[i_1 + k + 1, j_1, i_2, j_2], & \forall k \in \{1, \ldots, i_2 - i_1\} \\ 1 + B[i_1, j_1, i_2, j_1 + k] + B[i_1, j_1 + k + 1, i_2, j_2], & \forall k \in \{1, \ldots, j_2 - j_1\} \end{cases} \]

（另一种等价写法是把「所有单方格块的切割数为 0」作为基准，再在合并时通过判断两块是否同为干净/咬破来确定父块是否「纯」，从而避免单独维护「纯块」检测表。）

(c) 子问题求解顺序：按 \((i_2 - i_1 + 1)(j_2 - j_1 + 1)\) 的递增顺序求解。即先解决所有最小子问题（例如只含一个方格的块），逐步构建 DP 数组，直到求出覆盖整张纸的结果 \(B[1, 1, m, n]\)。

(d) 时间复杂度分析：两种答案均可接受：\(O((m + n)m^2 n^2)\) 与 \(O(m^3 n^3)\)。

共有 \(O(m^2 n^2)\) 个子问题：\((i_1, j_1)\) 有 \(O(mn)\) 种取法，\((i_2, j_2)\) 有 \(O(mn)\) 种取法。对每个子问题，我们最多考察 \(m\) 个水平分割点与 \(n\) 个垂直分割点；一次分割会产生两个已解决的小子问题，故只需找出最优分割，耗时 \(O(n + m)\)。

此外，每个子问题还需检测「纯块」基准情形（全为干净或全为咬破）。暴力检测耗时 \(O(mn)\)，因此每个子问题耗时 \(O(mn + (m + n)) \to O(mn)\)。

这个每子问题的 \(O(mn)\) 因子可被降到 \(O(m + n)\)（不要求也可获满分）：可预先计算每个子矩阵的「纯度」并存入表中，用前缀和可在 \(O(mn)\) 时间内完成该预处理。若能在 \(O(1)\) 时间内判定纯度（经预处理），则整体时间可达 \(O((m + n)m^2 n^2)\)。

或者，可初始化所有单方格块的切割数为 0；若存在某次切割使得结果两块切割数都为 0，且这两块类型相同（同为干净或同为咬破，任取一块的一个方格与另一块比较即可），则自身也是纯块。这样可完全省去前述预处理，仍达到 \(O((m + n)m^2 n^2)\)。

(e) 空间复杂度分析：必须存储整个递推用的 DP 数组，故空间复杂度为 \(O(m^2 n^2)\)。

本题存在本地解答（notebook 中已给出参考实现），完整代码与算法说明如下。

Q1. Longest Increasing Subsequence

思路：维护 \(dp[i]\) 表示以位置 \(i\) 结尾的最长递增子序列长度，同时用 prev[i] 记录最优转移的前驱下标。填完 dp 后，找到 dp 值最大的位置作为终点，沿 prev 倒序回溯并反转得到实际子序列。

def longest_increasing_subsequence(arr, n):
    # compute the DP array
    dp = [1] * n
    prev = [i for i in range(n)]
    for i in range(n):
        for j in range(i):
            if arr[i] > arr[j] and dp[i] <= dp[j]:
                dp[i] = dp[j] + 1
                prev[i] = j
    # reconstruct the sequence
    end = dp.index(max(dp))
    sequence = []
    while prev[end] != end:
        sequence.append(arr[end])
        end = prev[end]
    sequence.append(arr[end])
    sequence.reverse()
    return sequence

Q2. Edit Distance / Global Alignment

思路：先按递推填 dp 表（删除 +1、插入 +1、替换/匹配 +diff），再从 \((n,m)\) 回溯到 \((0,0)\)，根据哪条边的代价等于 \(dp[i][j]\) 决定对齐方式，并同时构建 x_align 与 y_align，最后反转。

def edit_distance(x, y):
    n = len(x)
    m = len(y)
    dp = []
    def diff(i, j):
        return 1 if x[i - 1] != y[j - 1] else 0
    # base cases
    for i in range(n + 1):
        dp.append([-1] * (m + 1))
    for i in range(n + 1):
        dp[i][0] = i
    for j in range(m + 1):
        dp[0][j] = j
    # compute recurrence
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            by_deletion = dp[i - 1][j] + 1
            by_insertion = dp[i][j - 1] + 1
            by_substitution = dp[i - 1][j - 1] + diff(i, j)
            dp[i][j] = min(by_deletion, by_insertion, by_substitution)
    # Backtrace to compute the optimum alignment:
    x_align, y_align = "", ""
    i, j = n, m
    while (i, j) != (0, 0):
        deletion = dp[i-1][j] + 1 if i > 0 else float("inf")
        insertion = dp[i][j-1] + 1 if j > 0 else float("inf")
        substitution = (dp[i-1][j-1] + diff(i, j)) if i > 0 and j > 0 else float("inf")
        moves = [
            (deletion, (i-1, j)),
            (insertion, (i, j-1)),
            (substitution, (i-1, j-1)),
        ]
        prev_i, prev_j = min(moves)[1]
        x_align += x[i-1] if prev_i == i-1 else '-'
        y_align += y[j-1] if prev_j == j-1 else '-'
        i, j = prev_i, prev_j
    return x_align[::-1], y_align[::-1]

正确性与复杂度要点：

• LIS：\(dp[i] = \max_{j<i,\ arr[j]<arr[i]} (dp[j]+1)\)，基准 \(dp[i]=1\)。时间 \(O(n^2)\)，额外空间 \(O(n)\)（dp 与 prev）。

• Edit Distance：递推 \(dp[i][j] = \min(dp[i-1][j]+1,\ dp[i][j-1]+1,\ dp[i-1][j-1]+diff(i,j))\)，基准 \(dp[i][0]=i\)、\(dp[0][j]=j\)。填表时间 \(O(nm)\)，回溯重建对齐 \(O(n+m)\)。空间 \(O(nm)\)。

测试会验证：返回的对齐两串等长、每串仅由原串加 gap 得到、且两串间不同列数等于编辑距离（与 pylev.levenshtein 结果一致）。