解题思路
本题要求把一段不含空格的小写英文字符串切分为若干“词元”，并最大化：
所有词元的置信度分数之和 + 相邻词元之间的转移加分之和。
若无法完全用词表中的词覆盖整句，则输出 0。
核心算法：动态规划（DP）
P3713.第3题-大模型分词
题目内容
您正在为一种罕见的语言构建一个专用的大语言模型。由于训练样本缺失，传统BPE等标准的分词器效果不佳，使得大模型推理生成的句子不理想。
幸运的是，一位语言学家为罕见的语言的已知词根和词缀(我们统称为“词元"或“Token”)都标注了一个“置信度”分数，这个分数代表了该词元作为一个“独立单位”的合理性，同时，语言学家还总结出了一个转移分数表，表示当前词元选择对下一个词元"置信度"的影响。
您的任务是设计并实现一个“最优分词器”，它能将输入的罕见语言句子(一个不含空格的英文小写字符多也串)切分成一系列词元，并使得所有词元的置信度分数之和达到最大，从而帮助大语言模型在后续处理中能够输出更合理的句子
输入描述
第一行输入待分词的字符串 text，假设只包含英文小写字母；
接着输入词典词条数 n；
然后输入n行，每一行包含一个单词和对应的分值，以空格分隔。
第 n+3 行为转移分数的个数 m。
随后m行为转移分数数据。包括起始词、下一个词、转移分数加分X。以空格分隔。
参数范围说明：
- 0<len(text)≤100
- −100≤ 词典中单词的得分 ≤100
- −100≤ 词汇表置信度分数P≤100
- 输入的字符串都是英文小写字母
- 0<词汇表大小 n≤100
输出描述
返回最高的分词得分，若根据已知间汇表无法拆分则返回0、我们约定若切分成一系列词元中含有不在已知词汇表中的词，则最终得分为0。
样例1
输入
applepie
2
pen 3
apple 10
2
pen apple 5
pie apple 2
输出
0
说明
text中的字符不能和词典词条匹配出切分结果，无法计算得分。
样例2
输入
goodeats
4
good 15
goo 12
deats 14
eats 10
1
good eats -5
输出
26
说明
切分为["good","eats"] 的总分=15+10−5=20；
切分为 ["goo","deats"] 的总分=12+14=26；
所以最大得分为 26。
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
