当前位置:首页 > 开发 > 编程语言 > 算法 > 正文

动态规划算法学习十例之七

发表于: 2012-10-04   作者:128kj   来源:转载   浏览:
摘要: 一、最长公共子序列(LCS)问题:    给定两个序列 X = {x1, x2, ......, xm } 和 Y = {y1, y2, ......, yn },找出 X 和 Y 的最长公共子序列。    一个给定序列的子序列是在该序列中删去若干个元素后得到的序列。给定两个序列 X 和 Y ,当另一序列 Z 既是 X 的子序列又是 Y 的子序列时,
一、最长公共子序列(LCS)问题:
   给定两个序列 X = {x1, x2, ......, xm } 和 Y = {y1, y2, ......, yn },找出 X 和 Y 的最长公共子序列。

   一个给定序列的子序列是在该序列中删去若干个元素后得到的序列。给定两个序列 X 和 Y ,当另一序列 Z 既是 X 的子序列又是 Y 的子序列时,称 Z 是序列 X 和 Y 的公共子序列。

例如,若 X = {A, B, C, B, D, A, B },
             Y = {B, D, C, A, B, A },
序列{B, C, A }是 X 和 Y 的一个公共子序列,序列{B, C, B, A }也是 X 和 Y 的一个公共子序列,且为最长公共子序列。

最长公共子序列问题具有最优子结构性质。
   设序列 X = {x1, x2, ......, xm } 和 Y = {y1, y2, ......, yn }的最长公共子序列为 Z = {z1, z2, ......, zk}
则(1) 若 xm = yn ,则 zk = xm = yn ,且 Zk-1 是 Xm-1 和 Yn-1 的最长公共子序列。
   (2) 若 xm != yn 且 zk != xm ,则 Z 是 Xm-1 和 Y 的最长公共子序列。
   (3) 若 xm != yn 且 zk != yn ,则 Z 是 X 和 Yn-1 的最长公共子序列。
其中:
Xm-1 = {x1, x2, ......, xm-1 }; Yn-1 = {y1, y2, ......, yn-1}; Zk-1 = {z1, z2, ......, zk-1}。

    引进一个二维数组C,用C[i,j]记录Xi与Yj的LCS的长度,如果我们是自底向上进行递推计算,那么在计算C[i,j]之前,
C[i-1,j-1], C[i-1,j]与C[i,j-1]均已计算出来。此时我们根据x[i]=y[j]还是x[i]≠y[j],就可以计算出C[i,j]:

若x[i]=y[j],则执行C[i,j]=C[i-1,j-1]+1;若x[i]≠y[j],则根据:
C[i-1,j]≥C[i,j-1],则C[i,j]取C[i-1,j];否则C[i,j]取C[i,j-1]。

    为了构造出LCS,使用一个m×n的二维数组b,b[i,j]记录C[i,j]是通过哪一个子问题的值求得的,以决定搜索的方向:
若C[i-1,j]≥C[i,j-1],则b[i,j]中记入“0”;
若C[i-1,j] < C[i,j-1],则b[i,j]中记入“-1”;

import java.util.Stack;
import java.util.Random;
public class LCSProblem    
{   
   private char[] x;
   private char[] y;
   int b[][];
   int c[][];//C[i,j]记录Xi与Yj的LCS的长度

   public LCSProblem(String s1,String s2){
       x=new String(" "+s1).toCharArray();
       y=new String(" "+s2).toCharArray();
       b=new int[x.length][y.length];
       c=new int[x.length][y.length];
   }


    public static void main(String[] args)   
    {   
        //LCSProblem lcs=new LCSProblem("pjwrbilcerzypsedamgk","kqeddkogpazssnnr");
        LCSProblem lcs=new LCSProblem("programming","contest");
        System.out.println(lcs.getLength());   
           
        lcs.Display();   
       

    }   
       
    private int  getLength()   //计算c[i][j],从前往后计算
    {   
        
        for(int i=1; i< x.length; i++)   
        {   
            for(int j=1; j< y.length; j++)   
            {   
                if( x[i] == y[j])   
                {   
                    c[i][j] = c[i-1][j-1] + 1;   
                    b[i][j] = 1;   
                }   
                else if(c[i-1][j] >= c[i][j-1])   
                {   
                    c[i][j] = c[i-1][j];   
                    b[i][j] = 0;   
                }   
                else  
                {   
                    c[i][j] = c[i][j-1];   
                    b[i][j] = -1;   
                }   
            }   
        }      
           
     return c[x.length-1][y.length-1];
    }   
       
    public  void Display(){//输出最长公共子序列
       int i = x.length-1, j = y.length-1;
       Stack< Character> sta=new Stack< Character>();
     
        while (i>=1&& j >=1){
            if (b[i][j]==1) {
                sta.push(x[i]);
                i--;
                j--;
            } else if (b[i][j]==0)
                i--;
            else
                j--;
        }
       while(!sta.empty())
        System.out.print(sta.pop()+" ");
    } 
   
 
}  

运行:
2
o n

二、例:
   回文词是一种对称的字符串。任意给定一个字符串,通过插入若干字符,都可以变成回文词。现在的任务是,求出将给定字符串变成回文词所需要插入的最少字符数。比如 “Ab3bd”插入2个字符后可以变成回文词“dAb3bAd”或“Adb3bdA”,但是插入少于2个的字符无法变成回文词。

[输入]:
第一行:字符串的长度N(3 <= N <= 5000)
第二行:需变成回文词的字符串
[输出]:
将给定字符串变成回文词所需要插入的最少字符数
[样例]:
Sample Input
5
Ab3bd

Sample Output
2

分析:
S和S' (注:S'是S的反串)的最长公共子串其实一定是回文的。这样我们就可以借助lcs来解决该题,即用s的长度减去lcs的值即可。
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

 public static void main(String[] args) throws Exception{
	BufferedReader in = new BufferedReader(new InputStreamReader (System.in));
	int total = Integer.parseInt(in.readLine());
	String string = in.readLine();
		System.out.println(total-LCS(string,new StringBuffer(string).reverse().toString()));
}

//返回两个string的lcs的长度
public static int LCS(String str1,String str2){
	short length1 = (short)str1.length();
	short length2 = (short)str2.length();
	short[][]result = new short [length1+1][length2+1];
	for(int i=0;i< length1;i++){
		result[i][0] = 0;
	}
	for(int i=0;i< length2;i++){
		result[0][i] = 0;
	}
	for(int i=1;i<=length1;i++){
      for(int j=1;j<=length2;j++){
		if(str1.charAt(i-1)==str2.charAt(j-1))
		 result[i][j] = (short)(result[i-1][j-1]+1);
		else
         result[i][j] = result[i-1][j]>result[i][j-1]?result[i-1][j]:result[i][j-1];
		}
	}
	return result[length1][length2];
 }
	

}


下载源码:

动态规划算法学习十例之七

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
1、最优二叉搜索树的动态规则算法 二叉搜索树是一颗满足如下条件的树: 1.每个节点包含一个键值 2.每
一、数组的最大子段和问题: 给定n个整数(可能为负数)组成的序列a[1],a[2],a[3],…,a[n],求该序列
凸多边形最优三角剖分 一凸8边形P的顶点顺时针为{v1,v2,… ,v8},任意两顶点间的线段的权重由矩阵
动态规划在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解
例一:计算二项式系数: 在排列组合里面,我们有下面的式子(很容易用组合的定义来证明): 这个式
例一: 给出N台电脑和K辆卡车,要求每辆卡车至少放一台电脑。问共有多少种放法运走这些电脑? 数据范
1,什么是动态规划(DP)? 非常重要!,不要认为概念不重要,理解的深刻,你才知道对于什么样的问
前言 最近帮同学写一个程序,给出100多个金额,用数组表示为money[1-100],再给出一个数额SUM。如果
动态规划方法是对解最优问题的一种方法,一种途径,并不是一种特殊的算法。 执行步骤: 1. 找出最优
和分治算法一样,动态规划是通过组合子问题的解而解决整个问题的。但是与分治算法不同的是,动态规
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号