题解 | 最优分词器（搬运@想回学校的打工人在研究求职打法，只是加注释方便学习）

from math import inf
# 输入处理
s = input() # 输入的字符串第一行：aababa
l = len(s) # 输入的字符串第一行，即需处理的字符串长度：6
dict_score = {} # 分词得分
trans_score = {} # 转移加分
n = int(input()) # 将输入的字符串第二行：4 转为整数
for i in range(n):
    s1, sc = input().split() # 将输入的字符串第3-n行，按空格切分
    dict_score[s1] = int(sc) # 构建分词得分字典
m = int(input()) # 将输入的字符串下一行：3 转为整数
for i in range(m):
    s1, s2, sc = input().split() # 将输入的字符串第-m行，按空格切分
    trans_score[(s1, s2)] = int(sc)  # （元组）：分数


dp = [[-inf] * l for i in range(l)]
# 列表推导式，构建一个元素=-inf的lxl维矩阵，还可以写为dp=np.ones((l,l))*(-inf)
# 初始化
# 初始化dp数组为负无穷 dp[i][j]表示以第i个字符为上一次分割的字符串结尾，以第j个字符为上一次分割的字符串开头时的最优分割结果
for i in range(l):
    if s[: i + 1] in dict_score: # 查找key是否在字典中
        dp[i][0] = dict_score[s[: i + 1]]  # 初始化边界条件，如果s的前i个字母在字典中，则dp[i][0]为其对应分数

# 动态转移
ans = -inf  # 初始化答案
# 枚举一个切分方案 → 把它分成 上一个词 (s[k:j+1]) 和 当前词 (s[j+1:i+1]) → 更新状态。
for i in range(l):  # 枚举下一次分割可能的位置
    for j in range(i):  # 枚举上一次分割可能的结尾，即下一词的开头 j in range(0), j=0
        for k in range(j + 1):  # 枚举上一次分割可能的开头 k in range(1), k=0
            s1, s2 = s[k : j + 1], s[j + 1 : i + 1] # s1：上一个词 s2: 当前词
            if s1 in dict_score and s2 in dict_score: # 如果上次分割的结果和本次分割的结果均在字典中，更新结果
                dp[i][j + 1] = max(
                    dp[i][j + 1],
                    dp[j][k] + dict_score[s2] + trans_score[(s1, s2)] if (s1, s2) in trans_score else 0,
                )
for i in range(l):
    ans = max(ans, dp[l - 1][i])  # 找到所有“以最后一个字符结尾的切分方案”的最大值。
print(ans if ans != -inf else 0)  # 如果最后答案为-inf说明没有符合的切分，输出0