最長公共子序列LCS

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

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

最長公共子序列

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

3.對于狀態(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云服務器最長公共子序列最長公共子串最長遞增子序列 java最長相同子串

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

轉載請注明本文地址：http://systransis.cn/yun/72996.html

javascript 最長公共子序列

摘要：但不是和的最長公共子序列，而序列和也均為和的最長公共子序列，長度為，而和不存在長度大于等于的公共子序列。最長公共子序列給定序列和，從它們的所有公共子序列中選出長度最長的那一個或幾個。為和的最長公共子序列長度。最長公共子序列（Longest Common Subsequence LCS）是從給定的兩個序列X和Y中取出盡可能多的一部分字符，按照它們在原序列排列的先后次序排列得到。LCS問...

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

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

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

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

IamDLY 2019-07-30 16:49 評論0 收藏0
算法設計 - LCS 最長公共子序列&&最長公共子串 &&LIS 最

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

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

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

Karuru 2019-08-14 15:07 評論0 收藏0