本文涉及知识点

C++动态规划

LeetCode2746. 字符串连接删减字母

给你一个下标从 0 开始的数组 words ，它包含 n 个字符串。
定义 连接 操作 join(x, y) 表示将字符串 x 和 y 连在一起，得到 xy 。如果 x 的最后一个字符与 y 的第一个字符相等，连接后两个字符中的一个会被 删除 。
比方说 join(“ab”, “ba”) = “aba” ， join(“ab”, “cde”) = “abcde” 。
你需要执行 n - 1 次 连接 操作。令 str0 = words[0] ，从 i = 1 直到 i = n - 1 ，对于第 i 个操作，你可以执行以下操作之一：
令 stri = join(stri - 1, words[i])
令 stri = join(words[i], stri - 1)
你的任务是使 strn - 1 的长度 最小 。
请你返回一个整数，表示 strn - 1 的最小长度。
示例 1：
输入：words = [“aa”,“ab”,“bc”]
输出：4
解释：这个例子中，我们按以下顺序执行连接操作，得到 str2 的最小长度：
str0 = “aa”
str1 = join(str0, “ab”) = “aab”
str2 = join(str1, “bc”) = “aabc”
str2 的最小长度为 4 。
示例 2：
输入：words = [“ab”,“b”]
输出：2
解释：这个例子中，str0 = “ab”，可以得到两个不同的 str1：
join(str0, “b”) = “ab” 或者 join(“b”, str0) = “bab” 。
第一个字符串 “ab” 的长度最短，所以答案为 2 。
示例 3：
输入：words = [“aaa”,“c”,“aba”]
输出：6
解释：这个例子中，我们按以下顺序执行连接操作，得到 str2 的最小长度：
str0 = “aaa”
str1 = join(str0, “c”) = “aaac”
str2 = join(“aba”, str1) = “abaaac”
str2 的最小长度为 6 。
提示：
1 <= words.length <= 1000
1 <= words[i].length <= 50
words[i] 中只包含小写英文字母。

动态规划

动态规划的状态表示

n = word.length
dp[i][ch1][ch2] 表示操作i次后，已经连接的串以ch1开始，ch2结尾的最短长度。
空间复杂度：O(n$\sum \sum$) $\sum$是字符集的大小，本题是26。
可以用滚动向量 pre = dp[i] cur = dp[i+1]

动态规划的填表顺序

i = 0 to n-2

动态规划的转移方程

s = words[i+1]
连接方式一：
MinSelf(cur[ch1][s.back()] ,pre[ch1][ch2] + s.length() - (ch2== s[0]))
连接方式二：
MinSelf(cur[s[0]][ch2],pre[ch1][ch2] + s.length() - (ch1== s.back()))
单个状态转移的时间复杂度O(1)，总时间复杂度和空间复杂度相同。

动态规划的初始化

s = words[0]
pre[s[0]][s.back()] = s.length
其它全部是 INT_MAX/2

动态规划的返回值

pre的最小值

代码

核心代码

class Solution {
		public:
			int minimizeConcatenatedLength(vector<string>& words) {
				const int N = words.size();
				vector<vector<int>> pre(26, vector<int>(26, INT_MAX / 2));
				pre[words[0][0] - 'a'][words[0].back() - 'a'] = words[0].length();
				for (int i = 0; i + 1 < N; i++) {
					vector<vector<int>> cur(26, vector<int>(26, INT_MAX / 2));
					const auto& s = words[i + 1];
					for (int i1 = 0; i1 < 26; i1++) {
						for (int i2 = 0; i2 < 26; i2++) {
							cur[i1][s.back() - 'a'] = min(cur[i1][s.back() - 'a'], pre[i1][i2] + (int)s.length() - (i2 + 'a' == s[0]));
							cur[s[0]-'a'][i2] = min(cur[s[0] - 'a'][i2], pre[i1][i2] + (int)s.length() - (i1 + 'a' ==s.back()));
						}
					}
					pre.swap(cur);
				}
				int ans = INT_MAX;
				for (const auto& v : pre) {
					ans = min(ans, *min_element(v.begin(),v.end()));
				}
				return ans;
			}
		};

单元测试

vector<string> words;
		TEST_METHOD(TestMethod11)
		{
			words = { "aa", "ab", "bc" };
			auto res = Solution().minimizeConcatenatedLength(words);
			AssertEx(4, res);
		}
		TEST_METHOD(TestMethod12)
		{
			words = { "ab","b" };
			auto res = Solution().minimizeConcatenatedLength(words);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod13)
		{
			words = { "aaa","c","aba" };
			auto res = Solution().minimizeConcatenatedLength(words);
			AssertEx(6, res);
		}