「太长，不看」版本
令 $s$ 表示要划分的字符串，$s(i..j)$ 表示从 $s_i$ 到 $s_{j - 1}$ 的长为 $j - i$ 的子串。令 $dp(i)$ 表示字符串 $s(0..i)$ 可以被划分成的最小单词数。令 $f:\text{char}\to S{\text{string}}$ 表示一个从「单词最后一个字母」到「整个单词」的映射。例如，$f(\text{l}) = S{\text{real, soul, peal …}}$。有
$$
dp(i) = \min_{f(s(i)) \ne \phi,\; w\in f(s(i))}^{(w.\text{len} \le i) \wedge (w = s(i - w.\text{len}..i))}(dp(i-w.\text{len}) + 1)
$$
$$
dp(i) = \inf,\;\;\text{if}\; f(s(i)) = \phi
$$
$$
dp(0) = 0
$$
解释
要求把一个字符串 str 切分成单词集合的最小数量方法，可以这样看：最后一个字母一定在一个单词里。这个单词被切分出去以后，剩下了一个子字符串。那么原字符串最小切分方法就是子字符串的最小切分数量 + 1（加上刚才切分出去的一个单词）。可能存在多种切分出最后一个单词的方法，所以应该选取多种方法中结果最小的那一个。如果一个字符串不可切分，那么可以把它的值设为 $\inf$，这样选取最小值时就不会选到它了。
问题是怎么查找到可以切出的单词。为了提高查找的效率，可以使用一个从单词最后一个字母映射到单词的哈希字典。
单词必须等于 str 的一个尾子串才能被切分，细化到代码中分为三步，第一步是查找所有以 s[i] 结尾的单词，第二步是筛选出其中等于 str 一个子串的单词，第三步是比较、取最小值。因为要加 1，所以 $\inf$ 的值不能取 numeric_limits<>::max()，否则会溢出。
代码
#include "bits/stdc++.h"
using namespace std;
using u64 = uint64_t;
int main() {
u64 t;
cin >> t;
for (u64 _ = 0; _ < t; ++_) {
string kText;
u64 n;
cin >> kText >> n;
unordered_multimap<char, string> WordDictionary;
for (u64 i = 0; i < n; ++i) {
string word;
cin >> word;
char const kBackChar = word.back();
WordDictionary.insert({kBackChar, move(word)});
}
// dp[i]: minimal division of kText(0..i), if not exist, it is kInf.
constexpr auto kInf = numeric_limits<u64>::max() / 2;
vector<u64> dp(kText.size() + 1, kInf);
dp[0] = 0;
for (u64 i = 1; i <= kText.size(); ++i) {
auto const [kBegin, kEnd] = WordDictionary.equal_range(kText[i - 1]);
for (auto iter = kBegin; iter != kEnd; ++iter) {
auto const &kWord = iter->second;
if (kWord.size() > i || kWord != string_view(&kText[i - kWord.size()], kWord.size())) {
continue;
}
if (dp[i] > dp[i - kWord.size()] + 1) {
dp[i] = dp[i - kWord.size()] + 1;
}
}
}
cout << dp.back() << '\n';
}
}
EOJ 这个数学公式支持有点渣啊……