【题目描述】
有一个很长的由小写字母组成字符串。为了便于对这个字符串进行分析，需要将它划分成若干个部分，每个部分都必须是字典中的一个单词。 出于减少分析量的目的，我们希望划分出的单词数越少越好。 你就是来完成这一划分工作的。
给出字符串和字典，输出最少的划分单词数。
【输入】
第 \(1\) 行，\(1\) 个字符串。（字符串的长度不超过 \(1000\)）
第 \(2\) 行，\(1\) 个整数 \(n\)，表示字典中单词的个数。（\(n≤100\)）
第 \(3\) 到 \(n+2\) 行，每行列出一个字典中的单词。（单词长度不超过 \(100\)）
【输出】
【输入样例】
realityour
5
real
reality
it
your
our
【输出样例】
2
【代码详解】
#include<iostream>
#include<cstring>
#include<string>
using namespace std;int n, dp[1005], m; // n: 词典大小，dp: 动态规划数组，m: 字符串长度
string s, ls[105]; // s: 目标字符串，ls: 词典字符串数组// 检查子串是否在词典中
bool chk(string s)
{for (int i = 1; i <= n; i++){if (s == ls[i]){return 1; // 找到匹配}}return 0; // 未找到匹配
}int main()
{cin >> s >> n; // 读入目标字符串和词典大小m = s.size(); // 获取字符串长度s = ' ' + s; // 在字符串前加一个空格，使下标从1开始memset(dp, 0x3f, sizeof(dp)); // 初始化dp数组为较大值dp[0] = 0; // 空字符串需要0个单词for (int i = 1; i <= n; i++){cin >> ls[i]; // 读入词典中的单词}for (int i = 1; i <= m; i++) // 遍历目标字符串的每个位置{for (int j = i; j >= 1; j--) // 从位置i向前遍历可能的子串{// 检查子串s[j:i]是否在词典中if (chk(s.substr(j, i - j + 1))){// 如果子串在词典中，更新dp[i]的最小值// dp[i] = min(当前最小值, dp[j-1] + 1)dp[i] = min(dp[i], dp[j - 1] + 1);}}}cout << dp[m]; // 输出组成整个字符串所需的最小单词数return 0;
}
【运行结果】
realityour
5
real
reality
it
your
our
2