我一直在努力从这个以下问题的书 。
某些字符串处理语言提供其将字符串转换成两块基元的操作。 由于该操作涉及复制原始的字符串，它需要n个单位的时间长度为n的串，而不管切割的位置。 假设，现在，要断线成许多碎片。 其中，断裂是由顺序可能会影响总的运行时间。 例如，如果你想在位置3和10以切割20个字符的字符串，那么在3位使第一切口即被的20 + 17 = 37，总成本，而这样做第一位置10具有20+更好的成本10 = 30。
我需要，鉴于米削减动态编程算法，找出切割一个字符串转换为m + 1个片的最小成本。
分而治之的方法似乎我这种问题的最好的之一。 这里是一个Java实现的算法：
注意 ：该阵列m应以升序进行排序（使用Arrays.sort(m); ）
public int findMinCutCost(int[] m, int n) {
int cost = n * m.length;
for (int i=0; i<m.length; i++) {
cost = Math.min(findMinCutCostImpl(m, n, i), cost);
}
return cost;
}
private int findMinCutCostImpl(int[] m, int n, int i) {
if (m.length == 1) return n;
int cl = 0, cr = 0;
if (i > 0) {
cl = Integer.MAX_VALUE;
int[] ml = Arrays.copyOfRange(m, 0, i);
int nl = m[i];
for (int j=0; j<ml.length; j++) {
cl = Math.min(findMinCutCostImpl(ml, nl, j), cl);
}
}
if (i < m.length - 1) {
cr = Integer.MAX_VALUE;
int[] mr = Arrays.copyOfRange(m, i + 1, m.length);
int nr = n - m[i];
for (int j=0; j<mr.length; j++) {
mr[j] = mr[j] - m[i];
}
for (int j=0; j<mr.length; j++) {
cr = Math.min(findMinCutCostImpl(mr, nr, j), cr);
}
}
return n + cl + cr;
}
例如 ：
int n = 20;
int[] m = new int[] { 10, 3 };
System.out.println(findMinCutCost(m, n));
将打印30
** 编辑 **
我已经实现了其他两种方法来回答这个问题的问题。
这种方法递归地削减总的最大块。 结果并不总是最好的解决方案，但是从性价比最好微不足道的最小割损差提供了一个不容忽视的增益（从我的测试+ 100000％的涨幅的次序）。
public int findMinCutCost2(int[] m, int n) {
if (m.length == 0) return 0;
if (m.length == 1) return n;
float half = n/2f;
int bestIndex = 0;
for (int i=1; i<m.length; i++) {
if (Math.abs(half - m[bestIndex]) > Math.abs(half - m[i])) {
bestIndex = i;
}
}
int cl = 0, cr = 0;
if (bestIndex > 0) {
int[] ml = Arrays.copyOfRange(m, 0, bestIndex);
int nl = m[bestIndex];
cl = findMinCutCost2(ml, nl);
}
if (bestIndex < m.length - 1) {
int[] mr = Arrays.copyOfRange(m, bestIndex + 1, m.length);
int nr = n - m[bestIndex];
for (int j=0; j<mr.length; j++) {
mr[j] = mr[j] - m[bestIndex];
}
cr = findMinCutCost2(mr, nr);
}
return n + cl + cr;
}
代替计算最低成本的，只是使用不同的指标和缓冲区。 由于这种方法在一定时间内执行，它总是返回n。 另外，该方法实际上一分为子字符串。
public int findMinCutCost3(int[] m, int n) {
char[][] charArr = new char[m.length+1][];
charArr[0] = new char[m[0]];
for (int i=0, j=0, k=0; j<n; j++) {
//charArr[i][k++] = string[j]; // string is the actual string to split
if (i < m.length && j == m[i]) {
if (++i >= m.length) {
charArr[i] = new char[n - m[i-1]];
} else {
charArr[i] = new char[m[i] - m[i-1]];
}
k=0;
}
}
return n;
}
注意 ：这个最后的方法可以很容易地修改以接受String str参数代替n并设置n = str.length() ，并返回一个String[]从数组charArr[][]
对于动态规划，我要求所有你真的需要知道的是状态空间应该是什么 - 如何代表的部分问题。
在这里，我们将一个字符串成M + 1个通过创建新的突破。 我要求，一个良好的状态空间是一组（A，B）对，其中a是一个子串和b的开始的位置是相同的子串的端部的位置，在最终计为断裂的数分解字符串。 与每对相关联的成本是打破它的最小成本。 若b <= A + 1，那么成本是0，因为没有更多的休息把英寸如果b大，则对于在该子下破可能位置是点a + 1，+ 2 ... b-1。 下破是要花费BA无论我们把它的，但如果我们把它位置k后休息的最低成本为（A，K）+（K，B）。
因此，为了与动态规划解决这个问题，建立一个表（A，B）最低的成本，在那里你可以考虑ķ制定出具有k段串游的成本 - 1点可能断裂，然后查找字符串的成本与至多为k - 1个部分。
对这种扩大的一种方法是通过创建一个表T开始[A，B]，并在该表中的所有条目设置为无穷大。 然后越过表再次和其中b <= A + 1个放T [A，B] = 0。这填补了表示其不需要进一步削减原来的字符串的段表项。 现在通过表和每个T [A，B]与B> A + 1考虑每一个可能的ķ扫描，使得<K <B，并且如果min_k（（场所之间长度和b）+ T [A，K] + T [K，b]）<T [A，b]中设置T [A，b]到该最小值。 这就承认，你现在知道的方式砍由T [A，K]和T代表的子[K，B]便宜，所以这给你一个更好的方式砍T [A，B]。 如果你现在重复你这样做m次 - 使用一个标准的动态规划回溯制定出解决方案。 如果保存k的每个T [A，B]在一个单独的表的最佳值，也可能有帮助。
Python代码：
mincost(n, cut_list) =min { n+ mincost(k,left_cut_list) + min(n-k, right_cut_list) }
import sys
def splitstr(n,cut_list):
if len(cut_list) == 0:
return [0,[]]
min_positions = []
min_cost = sys.maxint
for k in cut_list:
left_split = [ x for x in cut_list if x < k]
right_split = [ x-k for x in cut_list if x > k]
#print n,k, left_split, right_split
lcost = splitstr(k,left_split)
rcost = splitstr(n-k,right_split)
cost = n+lcost[0] + rcost[0]
positions = [k] + lcost[1]+ [x+k for x in rcost[1]]
#print "cost:", cost, " min: ", positions
if cost < min_cost:
min_cost = cost
min_positions = positions
return ( min_cost, min_positions)
print splitstr(20,[3,10,16]) # (40, [10, 3, 16])
print splitstr(20,[3,10]) # (30, [10, 3])
print splitstr(5,[1,2,3,4,5]) # (13, [2, 1, 3, 4, 5])
print splitstr(1,[1]) # (1, [1]) # m cuts m+1 substrings
这里是一个C ++实现。 其使用DP为O（n ^ 3）实现。 假定切割数组进行排序。 如果没有它需要为O（n ^ 3）时间对它进行排序，因此时间复杂保持相同。
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <limits.h>
using namespace std;
int main(){
int i,j,gap,k,l,m,n;
while(scanf("%d%d",&n,&k)!=EOF){
int a[n+1][n+1];
int cut[k];
memset(a,0,sizeof(a));
for(i=0;i<k;i++)
cin >> cut[i];
for(gap=1;gap<=n;gap++){
for(i=0,j=i+gap;j<=n;j++,i++){
if(gap==1)
a[i][j]=0;
else{
int min = INT_MAX;
for(m=0;m<k;m++){
if(cut[m]<j and cut[m] >i){
int cost=(j-i)+a[i][cut[m]]+a[cut[m]][j];
if(cost<min)
min=cost;
}
}
if(min>=INT_MAX)
a[i][j]=0;
else
a[i][j]=min;
}
}
}
cout << a[0][n] << endl;
}
return 0;
}
