題目描述

有一個很長的由小寫字母組成字符串。為了便于對這個字符串進行分析，需要將它劃分成若干個部分，每個部分稱為一個單詞。出于減少分析量的目的，我們希望劃分出的單詞數越少越好。你就是來完成這一劃分工作的。

輸入

第一行，一個字符串。（字符串的長度不超過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$ 跑完