本次作业精做了最长公共子序列计数问题与力扣《面试经典 150 题》「数组 / 字符串」部分的 LeetCode 135. 分发糖果 等两题。

最长公共子序列计数问题

洛谷 P2516 [HAOI2010] 最长公共子序列

思路

令 $dp[i][j]$ 表示 $X[1 \cdots i]$ 和 $Y[1 \cdots j]$ 的最长公共子序列长度，则状态转移方程为：
$$
dp[i][j] = \max\left(dp[i - 1][j], dp[i][j - 1], (dp[i - 1][j - 1] + 1)\times (X[i] = Y[j])\right)
$$
即可以从 $X$ 跳过一个字符或者从 $Y$ 跳过一个字符，最长公共子序列长度不变；当 $X$ 和 $Y$ 的下一个字符相同时，最长公共子序列长度在此基础上增加 $1$。

令 $num[i][j]$ 表示 $X[1 \cdots i]$ 和 $Y[1 \cdots j]$ 的最长公共子序列个数，则状态转移方程为：
$$
\begin{align}
num[i][j] = \sum(&num[i - 1][j], \\
&num[i][j - 1],\\
&(dp[i - 1][j - 1] + 1)\times (X[i] == Y[j]),\\
&-num[i - 1][j - 1] \times (dp[i][j] == dp[i - 1][j - 1]))
\end{align}
$$

即当前的最长公共子串的个数为可以转移来的状态的个数之和。特别地，当 $dp[i][j] = dp[i - 1][j]$ 时，因为 $dp$ 数组的性质，所以 $dp[i - 1][j]$ 和 $dp[i][j - 1]$ 必然等于 $dp[i - 1][j - 1]$，因此按照上述公式会重复计算 $num[i - 1][j - 1]$，需要减去重复计算的部分。

根据要求，课上的样例 $X = \text{ABCBDAB.}$，$Y = \text{BDCABA.}$ 的 $dp$ 和 $num$ 数组如下：（形式为 $dp[i][j]^{num[i][j]}$）

更详细地，$num$ 数组的转移过程如下：

$$
\begin{array}{|cc|cc|cc|cc|cc|cc|cc|cc|}
\hline
&&&&&&&&&&&&&&&\\
&&& A & &B & &C & &B & &D & &A & &B\\
\hline\\
&& &\downarrow&\searrow&&&&\searrow&&&&&&\searrow&\\
&B&\rightarrow&0^1 & &1^1 &\rightarrow &1^1 &\rightarrow &1^2 &\rightarrow &1^2 &\rightarrow &1^2 &\rightarrow &1^3\\
\hline\\
&& &\downarrow&&\downarrow&&\downarrow&&\downarrow&\searrow&&&&&\\
&D&\rightarrow&0^1 & &1^1 & \rightarrow &1^1 & \rightarrow&1^2 & &2^2 &\rightarrow &2^2 &\rightarrow &2^2\\
\hline\\
&& &\downarrow&&\downarrow&\searrow&&&&&\downarrow&&\downarrow&&\downarrow\\
&C&\rightarrow&0^1 & &1^1 & &2^1 &\rightarrow &2^1 &\rightarrow &2^3 &\rightarrow &2^3 &\rightarrow &2^3\\
\hline\\
&& \searrow&&&\downarrow&&\downarrow&&\downarrow&&\downarrow&\searrow&&&\\
&A& &1^1 &\rightarrow &1^2 & &2^1 &\rightarrow &2^1 &\rightarrow &2^3 & &3^3 &\rightarrow &3^3\\
\hline\\
&& &\downarrow&\searrow&&&\downarrow&\searrow&&&&&\downarrow&\searrow&\\
&B& &1^1 & &2^1 &\rightarrow &2^2 & &3^1 &\rightarrow &3^1 &\rightarrow &3^4 & &4^3\\
\hline\\
&& \searrow&\downarrow&&\downarrow&&\downarrow&&\downarrow&&\downarrow&\searrow&&&\downarrow\\
&A& &1^2 & &2^1 &\rightarrow &2^2 & &3^1 &\rightarrow &3^1 & &4^1 &\rightarrow &4^4\\
\hline
\end{array}
$$

代码

提交记录

#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 5007, mod = 1e8;
char X[maxn], Y[maxn];
long long lenx, leny, dp[2][maxn], num[2][maxn];
int main()
{
    scanf("%s%s", X + 1, Y + 1);
    lenx = strlen(X + 1) - 1, leny = strlen(Y + 1) - 1;
    for (int i = 0; i <= leny; ++i) num[0][i] = 1;
    for (int i = 1; i <= lenx; ++i)
    {
        memset(dp[i & 1], 0, sizeof(dp[i & 1])), memset(num[i & 1], 0, sizeof(num[i & 1]));
        num[i & 1][0] = 1;
        for (int j = 1; j <= leny; ++j)
        {
            if (X[i] == Y[j])
                if (dp[i & 1][j] == dp[i - 1 & 1][j - 1] + 1) num[i & 1][j] = (num[i & 1][j] + num[i - 1 & 1][j - 1]) % mod;
                else if (dp[i & 1][j] < dp[i - 1 & 1][j - 1] + 1) dp[i & 1][j] = dp[i - 1 & 1][j - 1] + 1, num[i & 1][j] = num[i - 1 & 1][j - 1];
            if (dp[i & 1][j] == dp[i - 1 & 1][j]) num[i & 1][j] = (num[i & 1][j] + num[i - 1 & 1][j]) % mod;
            else if (dp[i & 1][j] < dp[i - 1 & 1][j]) dp[i & 1][j] = dp[i - 1 & 1][j], num[i & 1][j] = num[i - 1 & 1][j];
            if (dp[i & 1][j] == dp[i & 1][j - 1]) num[i & 1][j] = (num[i & 1][j] + num[i & 1][j - 1]) % mod;
            else if (dp[i & 1][j] < dp[i & 1][j - 1]) dp[i & 1][j] = dp[i & 1][j - 1], num[i & 1][j] = num[i & 1][j - 1];
            if (dp[i & 1][j] == dp[i - 1 & 1][j - 1]) num[i & 1][j] = (num[i & 1][j] - num[i - 1 & 1][j - 1] + mod) % mod;
        }
    }
    printf("%lld\n%lld\n", dp[lenx & 1][leny], num[lenx & 1][leny]);
}

力扣 面试经典 150 题 - 数组 / 字符串

LeetCode 134. 加油站

思路

首先，如果所有加油站的油量和大于等于所有加油站的消耗量和，那么一定可以环绕一圈。否则，一定不能环绕一圈。

接着，我们先假设从第一个加油站出发，计算在每个加油站的油量（可能为负），那么我们会发现，有些加油站的油量为负，按照题目设定到达这些加油站就不能继续前进了。那么如何能够让所有加油站都能够到达呢？不难发现，只要可以从油量最少的加油站出发，这样就可以保证所有加油站都能够到达。因此直接返回最小油量的加油站编号即可。

代码

提交记录：116ms (61.75%) / 23.46MB (6.04%)

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        pre = [0]
        for i in range(len(gas)): pre.append(pre[-1] + gas[i] - cost[i])
        return -1 if pre[-1] < 0 else min(range(len(pre)), key=lambda i: pre[i])

LeetCode 135. 分发糖果

思路

经过观察样例我们可以发现，确定只分得 $1$ 颗糖果的孩子后，继续向两侧扩展便可以确定其他孩子的糖果分配方案。那么如何确定只分得 $1$ 颗糖果的孩子呢？不难发现处于“低谷”的孩子（即两侧孩子的评分均大于等于该孩子）只能获得 $1$ 颗糖果。因此，我们可以先确定所有只分得 $1$ 颗糖果的孩子，然后再向两侧扩展确定其他孩子的糖果分配方案。详细来说，当确定只获得 $1$ 颗糖果的孩子后，向左向右依次扩展，每次贪心地增加一颗糖果，直到位于“山峰”处的孩子（第一个不单调递增的孩子或者说两侧孩子的评分均小于等于该孩子）为止。需要注意的是，当扩展到位于山峰处的孩子时，为了左右两边的扩展结果均得到满足，需要取左右两边扩展结果的最大值。

根据上述过程填写糖果数量即可得到每个孩子分得糖果的数量数组，但本题只需要求出总糖果数量，因此我们并不需要真正得求出数量数组，这样便节约了空间开销，同时还避免了找到低谷的孩子后向回（向左）扩展的过程，而可以用一个变量（代码中是 down）来记录从山峰到低谷之间的孩子数量，当找到低谷时直接利用等差数列求和公式计算出这些孩子的糖果数量即可，以降低常数。

因为 ratings 数组的每个位置只会被遍历一次，因此时间复杂度为 $\mathrm O(n)$。遍历过程中无需存储每个孩子分得的糖果数量，只有常数数量的变量，因此空间复杂度为 $\mathrm O(1)$。

代码

提交记录：8ms (99.74%) / 16.74MB (90.18%)

class Solution {
public:
    int candy(vector<int>& ratings) {
        int ans = ratings.size() == 1 || ratings[0] <= ratings[1], down = 0, now = ans;
        for (int i = 1; i < ratings.size(); ++i)
            if (ratings[i - 1] <= ratings[i]) {
                if (down) ans += ((1 + down) * down >> 1) + max(down + 1, now) - now, now = 1, down = 0;
                if (ratings[i - 1] == ratings[i]) ans += (now = 1);
                else ans += ++now;
            } else ++down;
        if (down) ans += ((1 + down) * down >> 1) + max(down + 1, now) - now;
        return ans;
    }
};