本文共 2745 字，大约阅读时间需要 9 分钟。
问题描述：
某种字符串处理语言允许程序员将一个字符串拆分为两段。由于此操作需要复制字符串，因此要花费n个时间单位来将一个n个字符的字符串拆为两段。假定一个程序员希望将一个字符串拆分为多段，拆分的顺序会影响所花费的总时间。
例如，假定这个程序员希望将一个 20 个字符的字符串在第 2 个，第 8 个以及第 10 个字符后进行拆分（字符由左至右，从1开始升序编号）。如果她按由左到右顺序进行拆分，则第一次拆分花费 20 个时间单位，第二次拆掉分花费 18 个时间单位（在第 8 个字符处拆分 3 - 20 间的字符串）而第三次拆分花费 12 个时间单位，共花费 50 个时间单位。但如果她按由右至左的顺序进行查分，第一次拆分花费 12 个时间单位，第二次拆分花费 10 个时间单位，而第三次拆分花费 8 个时间单位，共花费 38 个时间单位。还可以按其他顺序，比如，她可以首先在第8个字符处进行拆分（时间20），接着在左边一段第 2 个字符处进行拆分（时间8），最后在右边一段第 10 个字符处进行拆分（时间12），总时间为 40 。
设计算法，对给定的拆分位置，确定最小代价的拆分顺序，更形式化地，给定一个 n 个字符的字符串 S 和一个保存 m 个拆分点的数组 L [ 1…m ]，计算拆分的最小代价，以及最优拆分序列。
❗算法思路❗：
字符串拆分可以看做是矩阵链乘法的一个翻版，只是要注意边界条件：两个拆分点之间有 1 个以上的元素才能进行拆分。
令，cost [ i ] [ j ] 表示从第 i 个拆分点到第 j 个拆分点的最小花费，需要满足 j - i ≥ 2 才可拆分。于是有如下递归式：
cost[i][j] = 0, j - i <= 1;cost[i][j] = min{cost[i,k] + cost[k,j] + L[j] - L[i] + 1}, j - i >= 2 算法实现：
#includeusing namespace std;#define n 4 //拆分点数目void BREAK_STRING(int L[], int Break[][n + 1]);void PRINT_BREAKS(int L[], int Break[][n + 1], int i, int j);int main(){ //先对拆分点按照升序排序 int L[n] = { 0, 3, 10, 30 }; //设置开始点为 0, 结尾点为 20, 中间两个点3，10为拆分点 int Break[n + 1][n + 1] = { 0 }; BREAK_STRING(L, Break); PRINT_BREAKS(L, Break, 1, n); return 0;}void BREAK_STRING(int L[], int Break[][n + 1]){ //cost[i][j]代表第 i 个拆分点到第 j 个拆分点所用的最小花费 int cost[n + 1][n + 1] = { 0 }; for (int len = 2; len <= n; ++len) { for (int i = 1; i <= n - len + 1; ++i) { int j = i + len - 1; if (j - i >= 2) { cost[i][j] = INT_MAX; } for (int k = i + 1; k <= j - 1; ++k) { int temp = cost[i][k] + cost[k][j] + L[j - 1] - L[i - 1]; if (temp < cost[i][j]) { cost[i][j] = temp; Break[i][j] = k; } } } }}void PRINT_BREAKS(int L[], int Break[][n + 1], int i, int j){ //按照顺序打印拆分点 if (j - i >= 2) { //既然是字符串拆分，那么拆分点 i 与 j 之间必须还有一个拆分点，所以 j - i 至少是 2 cout << L[Break[i][j] - 1] << " "; PRINT_BREAKS(L, Break, i, Break[i][j]); PRINT_BREAKS(L, Break, Break[i][j], j); }}
#includeusing namespace std;int main(){ //输入部分 cout << "请输入字符串的长度:" << endl; int len; cin >> len; cout << "请输入拆分点的个数与位置:" << endl; int num; cin >> num; int* spilt = new int(num + 2); for (int i = 1; i <= num; ++i) { cin >> spilt[i]; } spilt[0] = 0; spilt[num + 1] = len; int max_num = 999999; int cost[100][100]; //cost[spilt(i)][spilt(j)]存储最小代价 for (int j = 0; j <= num; ++j) { cost[spilt[j]][spilt[j + 1]] = 0; } for (int k = 2; k <= num + 1; ++k) { int q = num - k + 1; for (int i = 0; i <= q; ++i) { max_num = 999999; for (int j = 1; j < k; ++j) { int temp = cost[spilt[i]][spilt[i + j]] + cost[spilt[i + j]][spilt[i + k]] + spilt[i + k] - spilt[i]; if (temp < max_num) { cost[spilt[i]][spilt[i + k]] = temp; max_num = temp; } } } } cout << "最小代价: " << cost[0][spilt[num + 1]] << endl; return 0;}
转载地址：http://gttai.baihongyu.com/