7

某种字符串处理语言提供了一种将字符串分成两部分的原始操作。由于此操作涉及复制原始字符串，因此无论剪切的位置如何，长度为 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<j and 0<=w<=n

是对还是错？请帮忙，谢谢！

4

2 回答 2

3

我认为你的递归关系可以变得更好。这是我想出的，将 cost(i,j) 定义为将字符串从索引 i 剪切到 j 的成本。然后，

cost(i,j) = min {length of substring + cost(i,k) + cost(k,j) where i < k < j}
于 2015-11-12T23:22:05.513 回答
0 
 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)。

于 2013-11-29T13:03:37.230 回答