最長(zhǎng)公共子序列LCS

UnixAgain 發(fā)布于2019-08-16 14:26 / 2263人閱讀

摘要：最長(zhǎng)公共子序列動(dòng)態(tài)規(guī)劃問題，局部最小單元兩值是否相等，相等則從對(duì)角線上個(gè)位置處的數(shù)值，繼續(xù)狀態(tài)延續(xù)不相等則從上下兩個(gè)過去的位置找值保持延續(xù)，在上下兩個(gè)過去位置中保持著之前的最長(zhǎng)子序列。

最長(zhǎng)公共子序列

動(dòng)態(tài)規(guī)劃問題，局部最小單元：兩值是否相等，相等則從對(duì)角線上個(gè)位置處的數(shù)值+1，繼續(xù)狀態(tài)延續(xù)；不相等則從上下兩個(gè)過去的位置找值保持延續(xù)，在上下兩個(gè)過去位置中保持著之前的最長(zhǎng)子序列。

3.對(duì)于狀態(tài)的理解，保持最佳的，或者延續(xù)最佳的。

public class LongestCommonSubsequence {
    public static int compute(char[] str1, char[] str2) {
        int substringLength1 = str1.length;
        int substringLength2 = str2.length;
        int[][] opt = new int[substringLength1 + 1][substringLength2 + 1];
        for (int i = substringLength1-1; i >= 0; i--) {
            for (int j = substringLength2-1; j >= 0; j--) {
//                System.out.println(i);
//                System.out.println(j);
//                System.out.println("-*-  ");
                if (str1[i] == str2[j]) {
                    opt[i][j] = opt[i + 1][j + 1] + 1;
                } else {
                    opt[i][j] = Math.max(opt[i + 1][j], opt[i][j + 1]);
                }
            }
        }

        return opt[0][0];
    }
    public static int compute(String str1,String str2){
        return compute(str1.toCharArray(),str2.toCharArray());
    }
    public static void main(String[] args){
        String a1="abcd";
        String a2="bcead";
        int l1=compute(a1,a2);
        System.out.println(l1);
    }
}

GPU云服務(wù)器云服務(wù)器最長(zhǎng)公共子序列最長(zhǎng)公共子串最長(zhǎng)遞增子序列 java最長(zhǎng)相同子串

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/72996.html

相關(guān)文章

javascript 最長(zhǎng)公共子序列

摘要：但不是和的最長(zhǎng)公共子序列，而序列和也均為和的最長(zhǎng)公共子序列，長(zhǎng)度為，而和不存在長(zhǎng)度大于等于的公共子序列。最長(zhǎng)公共子序列給定序列和，從它們的所有公共子序列中選出長(zhǎng)度最長(zhǎng)的那一個(gè)或幾個(gè)。為和的最長(zhǎng)公共子序列長(zhǎng)度。最長(zhǎng)公共子序列（Longest Common Subsequence LCS）是從給定的兩個(gè)序列X和Y中取出盡可能多的一部分字符，按照它們?cè)谠蛄信帕械南群蟠涡蚺帕械玫健CS問...

Xufc 2019-08-22 13:52 評(píng)論0 收藏0
動(dòng)態(tài)規(guī)劃法（十）最長(zhǎng)公共子序列（LCS）問題

摘要：最長(zhǎng)公共子序列問題指的是求解兩個(gè)序列和的長(zhǎng)度最長(zhǎng)的公共子序列。當(dāng)然，可以看出，問題容易出現(xiàn)重疊子問題，這時(shí)候，就需要用動(dòng)態(tài)規(guī)劃法來(lái)解決。問題介紹 ??給定一個(gè)序列$X=$，另一個(gè)序列$Z=$滿足如下條件時(shí)稱為X的子序列：存在一個(gè)嚴(yán)格遞增的X的下標(biāo)序列${i_1,i_2,...,i_k}$，對(duì)所有的$j=1,2,...,k$滿足$x_{i_j}=z_j.$??給定兩個(gè)序列$X$和$Y$...

Ashin 2019-08-15 18:17 評(píng)論0 收藏0
動(dòng)態(tài)規(guī)劃法（十）最長(zhǎng)公共子序列（LCS）問題

摘要：最長(zhǎng)公共子序列問題指的是求解兩個(gè)序列和的長(zhǎng)度最長(zhǎng)的公共子序列。當(dāng)然，可以看出，問題容易出現(xiàn)重疊子問題，這時(shí)候，就需要用動(dòng)態(tài)規(guī)劃法來(lái)解決。問題介紹 ??給定一個(gè)序列$X=$，另一個(gè)序列$Z=$滿足如下條件時(shí)稱為X的子序列：存在一個(gè)嚴(yán)格遞增的X的下標(biāo)序列${i_1,i_2,...,i_k}$，對(duì)所有的$j=1,2,...,k$滿足$x_{i_j}=z_j.$??給定兩個(gè)序列$X$和$Y$...

IamDLY 2019-07-30 16:49 評(píng)論0 收藏0
算法設(shè)計(jì) - LCS 最長(zhǎng)公共子序列&&最長(zhǎng)公共子串 &&LIS 最

摘要：若且，則是和的最長(zhǎng)公共子序列若且，則是和的最長(zhǎng)公共子序列。遞歸結(jié)構(gòu)容易看到最長(zhǎng)公共子序列問題具有子問題重疊性質(zhì)。例如，在計(jì)算和的最長(zhǎng)公共子序列時(shí)，可能要計(jì)算出和及和的最長(zhǎng)公共子序列。雖是讀書筆記，但是如轉(zhuǎn)載請(qǐng)注明出處 http://segmentfault.com/blog/exploring/ .. 拒絕伸手復(fù)制黨本章講解： 1. LCS（最長(zhǎng)公共子序列）O(n^2)的時(shí)間復(fù)雜...

weizx 2019-08-14 12:07 評(píng)論0 收藏0
字符串處理文章outline

摘要：遇到問題查查，看看，大神的講解問問島胖君下面是我最近整理出來(lái)的關(guān)于字符串的文章的怎么翻譯匯集目錄非常希望強(qiáng)化博客的功能，比如分類，置頂。雖是讀書筆記，但是如轉(zhuǎn)載請(qǐng)注明出處 http://segmentfault.com/blog/exploring/ .. 拒絕伸手復(fù)制黨最近在看算法和語(yǔ)言，基本屬于看知識(shí) --> java實(shí)現(xiàn) --> 整理blog 這個(gè)路線。遇到問題查查st...

Karuru 2019-08-14 15:07 評(píng)論0 收藏0