`
128kj
  • 浏览: 604402 次
  • 来自: ...
社区版块
存档分类
最新评论

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

阅读更多
一、最长公共子序列(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];
 }
	

}


下载源码:
分享到:
评论

相关推荐

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

    标题 "动态规划算法学习十例之八" 暗示了我们将探讨动态规划这一重要的算法概念,特别是通过一个具体的例子——Matrix Chain Multiplication(矩阵链乘法)来深入理解。动态规划是一种解决复杂问题的有效方法,它...

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

    在这个“动态规划算法学习十例之九”的主题中,我们将聚焦于如何通过DP来解决实际问题。尽管描述部分没有提供具体的实例,但从标题来看,我们可以推测这是一个关于动态规划应用的系列教程的第九个例子。 动态规划的...

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

    在这个主题“动态规划算法学习十例之六”中,我们将探讨如何利用动态规划方法来解决实际问题。博文链接虽然未提供具体内容,但我们可以根据提供的文件名推测讨论的是一个具体的编程实例。 `Main.java`通常是一个...

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

    标题中的“动态规划算法学习十例之五”表明这篇内容主要关注的是计算机科学中的动态规划算法,这是一种在解决复杂问题时非常有效的优化方法。动态规划通常用于处理具有重叠子问题和最优子结构的问题,通过将大问题...

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

    在这个“动态规划算法学习十例之四”的主题中,我们将专注于背包问题的解决方案。背包问题是一个经典的计算机科学问题,它通常涉及在给定容量的背包中选择物品以最大化总价值。 首先,我们来了解动态规划的基本思想...

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

    在这个"动态规划算法学习十例之二"中,我们很可能会探讨两个具体的动态规划应用:一个可能涉及二项式系数计算,另一个可能是斐波那契数列的求解。下面,我们将深入这两个主题,理解它们背后的动态规划策略。 首先,...

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

    在这个“动态规划算法学习十例之一”的主题中,我们将会探讨动态规划的基本概念和一个具体的实例,通过分析`Test.java`源码来深入理解。 首先,动态规划的核心思想是将一个大问题分解为相互重叠的小问题,并通过...

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

    动态规划是一种重要的算法思想,广泛应用于解决复杂问题的优化,如最短路径、背包问题、最长公共子序列等。在本篇文章中,我们将探讨动态规划的精髓,并通过具体实例进行深入学习。博客链接提供了详细的解析,虽然...

    近似串匹配的动态规划算法

    在压缩包中的"近似串匹配问题"文件可能包含了这样的C语言实现,可以作为学习和理解近似串匹配动态规划算法的一个实例。 总结一下,近似串匹配的动态规划算法是一种高效的方法,通过Levenshtein距离或Hamming距离...

    国际大学生程序设计竞赛例题解.三:图论、动态规划算法、综合题专集

    三:图论、动态规划算法、综合题专集》是一本专门针对编程竞赛中的重要算法与问题解决策略的书籍。它涵盖了图论、动态规划以及综合题型,这些都是在竞赛中经常遇到并且至关重要的主题。下面将对这三个方面进行详细的...

    基于Python语言的“算法分析”课程设计——以动态规划算法为例.pdf

    在课程设计过程中,学生还将学习如何分析动态规划算法的时间复杂度和空间复杂度。例如,大多数动态规划解决方案的时间复杂度为O(n*W),其中n是物品数量,W是背包容量,而空间复杂度通常是O(n*W)或者更优,取决于是否...

    初识动态规划算法doc

    动态规划算法以其卓越的能力,成为应对这类问题的首选工具。它通过把复杂问题分解成更小、更易于管理的子问题,以递归的方式进行解决。这种方法不仅效率高,而且在很多情况下比其他算法(如贪婪算法或分治算法)更优...

    动态规划算法.

    在实际编程中,理解和掌握动态规划算法对于提高问题解决能力至关重要,因为它能够优雅地处理复杂度高且具有结构重叠的优化问题。在学习动态规划时,推荐阅读如《Introduction to Algorithms》等经典教材,它们深入浅...

    算法参考资料国际大学生程序设计竞赛例题解3图论·动态规划算法·综合题专集

    标题中提到的是“算法参考资料国际大学生程序设计竞赛例题解3 图论·动态规划算法·综合题专集”。这份资料集中的标题揭示了内容的几个关键点,即它是一份专门为解决算法问题而编写的参考资料,特别针对国际大学生...

    算法动态规划 专题 算法动态规划 专题 ppt

    **算法动态规划专题** 动态规划(Dynamic Programming,简称DP)是一种在计算机科学中解决最优化问题的算法技术,尤其在解决复杂度较高的多阶段决策问题时表现得尤为出色。它通过将大问题分解为小问题,并存储子...

    学习常用算法之(7)动态规划

    动态规划算法通常包含以下几个步骤: 1. 定义状态:识别问题中的关键状态,它们通常是问题的某个阶段的特性描述。 2. 状态转移方程:建立从一个状态到下一个状态的转换规则,这个方程描述了如何根据先前的状态计算...

    基于岭回归机器学习算法的项目成本预测研究——以A风景园林规划研究院规划设计项目为例.pdf

    "基于岭回归机器学习算法的项目成本预测研究——以A风景园林规划研究院规划设计项目为例.pdf" 本文研究主要集中在基于岭回归机器学习算法的项目成本预测研究,以A风景园林规划研究院规划设计项目为例。该研究的目的...

    编程语言算法100例

    本资源包含的100例算法涵盖了排序、搜索、图论、动态规划、递归等多个重要类别。 1. **排序算法**:包括冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等。排序算法是数据处理的基础,用于将一组无序的...

Global site tag (gtag.js) - Google Analytics