C# 记忆化搜索1代码O(n * 26 * 26)
public class Solution {
public int MinimizeConcatenatedLength(string[] words) {
int n = words.Length;
int[,,] cache = new int[n, 26, 26];
for (int i = 0; i < n; i++){
for (int j = 0; j < 26; j++){
for (int k = 0; k < 26; k++){
cache[i, j, k] = -1;
}
}
}
string word = words[0];
return word.Length + DFS(1, word[0] - 'a', word[^1] - 'a');
// 第i个字符串连接, 前面生成的字符串首字母j, 末尾字母k
int DFS(int i, int j, int k){
if (i == n) return 0;
if (cache[i, j, k] != -1) return cache[i, j, k];
string t = words[i];
// 放前面
int ans1 = DFS(i + 1, t[0] - 'a', k) - (t[^1] - 'a' == j ? 1 : 0);
// 放后面
int ans2 = DFS(i + 1, j, t[^1] - 'a') - (t[0] - 'a' == k ? 1 : 0);
cache[i, j, k] = Math.Min(ans1, ans2) + t.Length;
return cache[i, j, k];
}
}
}
C# 记忆化搜索2代码O(n * n)
public class Solution {
public int MinimizeConcatenatedLength(string[] words) {
int n = words.Length;
int[,] cache = new int[n, n];
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
cache[i, j] = -1;
}
}
string word = words[0];
return word.Length + DFS(0, 0);
// 当前拼接的字符串首字母来自words[i], 尾字母来自words[j]
int DFS(int i, int j){
// 由于是顺序处理,k即为下一个要处理的字符串, i, j最大值的下一个位置
int k = Math.Max(i, j) + 1;
if (k == n) return 0;
if (cache[i, j] != -1) return cache[i, j];
string t = words[k];
// 放后面
int ans1 = DFS(i, k) - (words[j][^1] == t[0] ? 1 : 0);
// 放前面
int ans2 = DFS(k, j) - (t[^1] == words[i][0] ? 1 : 0);
cache[i, j] = Math.Min(ans1, ans2) + t.Length;
return cache[i, j];
}
}
}