动态规划求字符串分割的最小成本

Question

一种字符串处理语言提供了一种将字符串分成两个部分的原始操作。由于这个操作涉及复制原始字符串，对于长度为n的字符串，无论切割的位置如何，都需要n个单位的时间。现在假设您想将一个字符串分成多个部分。断点的顺序可能会影响总运行时间。例如，如果您想在第3和第10个位置处截断20个字符的字符串，则在位置3进行第一次切割会产生总成本为20 + 17 = 37，而在位置10进行第一次切割的成本更好为20 + 10 = 30。

给出一个动态规划算法，它给出了在长度为n的字符串中的m个割线的情况下，将字符串分成m + 1个部分的最小成本。

此问题来自“算法”第6章6.9。

由于这个问题没有答案，这是我想到的。

将OPT(i,j,n)定义为打破字符串的最小成本，i为字符串的起始索引，j为结束索引，n为我可以使用的剩余切数。

以下是我的思路：

OPT(i,j,n) = min {OPT(i,k,w) + OPT(k+1,j,n-w) + j-i} for i<=k

以上是否正确？请帮忙确认，谢谢！

- CSnerd

---

实现并测试它？ - Bernhard Barker

@j_random_hacker 这个问题困扰我好几天了...我想不通为什么不需要n参数...如果你知道答案，请告诉我，谢谢！ - CSnerd

我明白为什么我的解释让你感到困惑了！不要把i和j看作字符串中的索引（位置），而是将它们视为块编号。字符串中有m+1个块，由需要进行的m次切割定义。例如，在这个例子中，有3个块：1-3、4-10和11-20（假设“在位置3处切割”意味着“在位置3之后切割”）。 - j_random_hacker

提示：这涉及到拥有一个包含每个块结束位置（或开始位置）的数组。 - j_random_hacker

你的问题已经在这里被问过（并得到了回答！）：https://dev59.com/kmLVa4cB1Zd3GeqPwnhV?rq=1 - Chthonic Project

Answer 1

我认为你的递归关系可以变得更好。以下是我想出的方法，定义cost(i,j)为从索引i到j切割字符串的成本。那么：

cost(i,j) = min {length of substring + cost(i,k) + cost(k,j) where i < k < j}

- KanwarG

Answer 2

 void  s_cut()    
  {
    int l,p;
    int temp=0;
    //ArrayList<Integer> al = new ArrayList<Integer>();
    int al[];
    Scanner s=new Scanner(System.in);
    int table[][];
    ArrayList<Integer> values[][];
    int low=0,high=0;
    int min=0;

    l=s.nextInt();
    p=s.nextInt();

    System.out.println("The values are "+l+"  "+p);

    table= new int[l+1][l+1];
    values= new ArrayList[l+1][l+1];
    al= new int[p];

    for(int i=0;i<p;i++)
    {
        al[i]=s.nextInt();

    }

    for(int i=0;i<=l;i++)
    for(int j=0;j<=l;j++)
        values[i][j]=new ArrayList<Integer>();

    System.out.println();

    for(int i=1;i<=l;i++)
        table[i][i]=0;
    //Arrays.s
    Arrays.sort(al);

    for(int i=0;i<p;i++)
    {
        System.out.print(al[i]+ "  ");

    }


    for(int len=2;len<=l;len++)
    {
        //System.out.println("The length is  "+len);

        for(int i=1,j=i+len-1;j<=l;i++,j++)
        {

            high= min_index(al,j-1);
            low= max_index(al,i);

            System.out.println("Indices are "+low+"  "+high);

            if(low<=high && low!=-1 && high!=-1)
            {

            int cost=Integer.MAX_VALUE;;

            for(int k=low;k<=high;k++)
            {
                //if(al[k]!=j)
                temp=cost;
                cost=Math.min(cost, table[i][al[k]]+table[al[k]+1][j]);

                if(temp!=cost)
                {
                    min=k; 
                    //values[i][j].add(al[k]);
                    //values[i][j].addAll(values[i][al[k]]);
                    //values[i][j].addAll(values[al[k]+1][j]);
                    //values[i][j].addAll(values[i][al[k]]);
                }

                //else
                //cost=0;
            }

            table[i][j]= len+cost;

            values[i][j].add(al[min]);
            //values[i][j].addAll(values[i][al[min]]);
            values[i][j].addAll(values[al[min]+1][j]);
            values[i][j].addAll(values[i][al[min]]);

            }

            else
                table[i][j]=0;

            System.out.println(" values are "+i+"  "+j+"  "+table[i][j]);
        }
    }

    System.out.println(" The minimum cost is "+table[1][l]);

    //temp=values[1][l];
    for(int e: values[1][l])
    {
        System.out.print(e+"-->");

    }

}

以上解决方案的时间复杂度为O(n^3)。

- Kumar Raja