【DP】单词的划分

题目描述

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

输入

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

输出

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

样例输入

realityour
5
real
reality
it
your
our

样例输出

2

提示

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

思路:

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

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

最后输出 $dp(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;
}

时间复杂度分析

状态总数为 $O(nk)$ $n$ 是字符串的长度，$k$ 是单词个数
每次转移是 $O(len)$ 的，$len$ 是单词的长度

所以时间复杂度是 $O(nklen)$ 因为他们最大的值都是 $100$, 所以时间复杂度大约就是 $O(n^3)$
完全可以过

Tips： 机器每秒进行大约 $10^8$ 次运算，在 $n=100$ 的情况下，最大运算量大约是 $O(100\times 100\times 100)$ 也就是 $10^6$ 次运算，后者是前者的 $100$ 倍，所以也是快的飞起，最大 $1ms$ 跑完