1254. 【动态规划】单词的划分

题目描述

思路

数组定义: dp[i] 表示原字符串的下标0 ~ i 的个数初始化: dp[0] = 0; 不考虑下标是0的情况状态转移方程:枚举字符串数组a[k] (k: 1 ~ n)if (可以连接)dp[i] = min(dp[i], dp[i - a[k].size()] - 1);答案: dp[Ans_Cin.size()]

Code

#include <iostream>
#include <string>
#include <vector>
#include <climits> // 使用INT_MAX
using namespace std;typedef string Word_t; // 定义Word_t为string类型
int main() {// 时间复杂度: o(n^3)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[i] 表示原字符串的下标0 ~ i 的个数初始化: dp[0] = 0; 不考虑下标是0的情况状态转移方程:枚举字符串数组a[k] (k: 1 ~ n)if (可以连接)dp[i] = min(dp[i], dp[i - a[k].size()] - 1);答案: dp[Ans_Cin.size()]*/// 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){//cout << "i - len = " << i - len << " i - 1 = " << i - 1 << '\n';string TempGetStr = Ans_Cin.substr(i - len, len); // 处理字符串//cout << TempGetStr << endl;if (TempGetStr == words[j]) // 如果相等dp[i] = min(dp[i], dp[i - len] + 1);}}}cout << dp[Size];return 0;
}