题目描述

有一个很长的由小写字母组成字符串。为了便于对这个字符串进行分析，需要将它划分成若干个部分，每个部分称为一个单词。出于减少分析量的目的，我们希望划分出的单词数越少越好。你就是来完成这一划分工作的。

输入

第一行，一个字符串。（字符串的长度不超过100）第二行一个整数n，表示单词的个数。（n<=100）第3~n+2行，每行列出一个单词。

输出

一个整数，表示字符串可以被划分成的最少的单词数。

样例输入

realityour
5
real
reality
it
your
our

样例输出

提示

（原字符串可拆成real+it+your或reality+our，由于reality+our仅为两个部分，因此最优解为2，另外注意，单词列表中的 每个单词都可以重复使用多次，也可以不用）

思路:

我们设 $d p (i)$ 表示原字符串的前 $i$ 个字符的单词最小划分总数
那么答案就是 $d p (n)$ $n$ 是原字符串的长度

初始化: $d p (0) = 0$ (因为一个单词也没有) $[d p (1)$ ~ $d p (n)]$ 为最大值
怎么转移呢?
对于每个长度，我们枚举所有的单词，我们可以使用 string 的 substr 函数求出末尾的字串，如果当前末尾的字串和当前枚举的单词可以对得上，那么我们就选这个单词
$\min(dp(i), dp(i - len) + 1)$
否则我们就不动这个单词

最后输出 $d p (n)$ 即可

代码

#include <iostream>
#include <string>
#include <vector>
#include <climits> // 使用INT_MAX
using namespace std;typedef string Word_t; // 定义Word_t为string类型
int main() {Word_t Ans_Cin;cin >> Ans_Cin; // 输入单词int n; // 单词个数cin >> n; // 输入单词个数vector<Word_t> words(n + 1); // 定义单词数组for (int i = 1; i <= n; ++i) cin >> words[i]; // 输入单词// dp第一步: 初始化vector<int> dp(Ans_Cin.size() + 1, INT_MAX - 10);dp[0] = 0;// dp第二步: 求解问题int Size = Ans_Cin.size(); // 长度for (int i = 1; i <= Size; i++){for (int j = 1; j <= n; j++){int len = words[j].size();if (i - len >= 0){string TempGetStr = Ans_Cin.substr(i - len, len); // 处理字符串if (TempGetStr == words[j]) // 如果相等dp[i] = min(dp[i], dp[i - len] + 1);}}}cout << dp[Size];return 0;
}