周赛250915

时隔多日再才重新开启周赛。这场DP居多。

T2-3290. 最高乘法得分

题目大意：

给定两个数组 a 和 b，数组 a 长度为 4，数组 b 长度至少为 4。需要从 b 中选择 4 个递增下标 i0 < i1 < i2 < i3，计算 a[0] * b[i0] + a[1] * b[i1] + a[2] * b[i2] + a[3] * b[i3]，并返回最大得分。

代码实现思路：

  • 使用动态规划的思想解决问题。定义 f[i][j] 表示在前 i 个元素中选择了 j 个数时的最大得分。
  • 初始化 f[0][0] = 0，表示在没有元素的情况下选择 0 个数时得分为 0，其余情况初始化为负无穷大。
  • 遍历数组 b，对于每一个位置 i，我们可以选择保留当前状态（即不选第 i 个元素，继承上一个状态的值），或者选择第 i 个元素（更新当前状态，计算乘积并加到上一个状态 f[i-1][j-1] 中）。
  • 最后，结果就是从长度为 4 的选择中得到的最大得分 max(f[i][4])。
class Solution:
    def maxScore(self, a: List[int], b: List[int]) -> int:
        n = len(b)

        f = [[-inf]*5 for _ in range(n + 1)]  # f[i][j] 表示 b 中 前 i 个数字(不包括i)中选 j 个可以获得的最大得分
        f[0][0] = 0

        for i in range(1, n + 1):
            for j in range(min(4, i) + 1):
                f[i][j] = f[i-1][j]
                if j:
                    f[i][j] = max(f[i][j], f[i-1][j-1] + a[j - 1] * b[i - 1])
        
        return max(f[i][4] for i in range(4, n +  1))

T3&4-3291. 形成目标字符串需要的最少字符串数 I

题目大意：

给定一个字符串数组 words 和一个目标字符串 target，需要通过连接 words 中的有效前缀字符串组成目标字符串 target。要求计算连接有效字符串形成 target 所需的最少字符串数量。如果无法组成 target，返回 -1。

代码实现思路：

  • 使用 Z 函数 计算 words 中每个字符串与 target 对应位置的最长匹配前缀，得到每个位置能匹配的最大长度 nxt 数组。
  • 动态规划数组 f[i] 表示到达 target 的第 i 个字符所需的最少字符串数量，初始时 f[0] = 0，表示到达初始位置需要 0 个字符串。
  • 遍历 target，如果某个位置无法通过前面的组合到达，则返回 -1；否则根据前面的匹配情况不断更新 f 数组，记录当前能够延伸的最长有效前缀 last。
  • 在遍历过程中，如果找到一个位置 i，可以用更少的字符串覆盖更长的前缀，则更新 f 数组和 last。
  • 最后返回 f[n]，即完整匹配 target 所需的最少字符串数。
def z_function(s):
    n = len(s)
    z = [0] * n 
    l, r = 0, 0

    for i in range(1, n):
        if i<=r and z[i - l] < r - i + 1:
            z[i] = z[i-l]
        else:
            z[i] = max(0, r - i  + 1)
            while i + z[i] < n and s[z[i]] == s[i + z[i]]:
                z[i] += 1

        if i + z[i] - 1 > r:
            l, r = i, i + z[i] - 1

    return z

class Solution:
    def minValidStrings(self, words: List[str], target: str) -> int:
        n = len(target)
        nxt = [0] * n 
        for w in words:
            s = w + '#' + target
            z = z_function(s)
            for i in range(n):
                nxt[i] = max(nxt[i], z[i + len(w) + 1])
        
        f = [-1] * (n + 1)
        f[0] = 0
        last = 0 # 所有 words 可以拓展到的target的最长长度

        for i in range(n):
            if f[i] == -1:
                continue
            if i > last:
                return -1
            
            nx = nxt[i]
            if i + nx > last:
                for j in range(last + 1, i + nx + 1):
                    f[j] = f[i] + 1
                last = i + nx
            if last == n:
                break
        return f[n]