392.判斷子序列：

初始思路：

????????

????????左為判斷公共子序列，右為判斷子序列，感覺(jué)代碼完全可以套用，如果公共子序列的長(zhǎng)度是較短的字符串的長(zhǎng)度的話即輸出true，如果不是即輸出false。

class Solution {
    public boolean isSubsequence(String s, String t) {
        if(s.length()==0&&t.length()==0){return true;}
        if(t.length()==0){return false;}
        char[] sc = s.toCharArray();
        char[] tc = t.toCharArray();
        int length = sc.length<tc.length?sc.length:tc.length;
        int[][] dp = new int[sc.length+1][tc.length+1];
        int result = 0;
        for(int i = 1;i<sc.length+1;i++){
            for(int j = 1;j<tc.length+1;j++){
                if(sc[i-1]==tc[j-1]){
                    dp[i][j] = dp[i-1][j-1]+1;
                }else{
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
                result = Math.max(result,dp[i][j]);
            }
        }
        if(result==length){return true;}
        return false;
    }
}

題解復(fù)盤(pán)：?

? ? ? ? 完全不一樣的思路，一個(gè)新的操縱方法：編輯距離！

動(dòng)態(tài)規(guī)劃五部曲：

1）確定dp數(shù)組（dp table）以及下標(biāo)的含義：

dp[i][j] 表示以下標(biāo)i-1為結(jié)尾的字符串s，和以下標(biāo)j-1為結(jié)尾的字符串t，相同子序列的長(zhǎng)度為dp[i][j]

2）確定遞推公式：

if (s[i - 1] == t[j - 1])，那么dp[i][j] = dp[i - 1][j - 1] + 1;，因?yàn)檎业搅艘粋€(gè)相同的字符，相同子序列長(zhǎng)度自然要在dp[i-1][j-1]的基礎(chǔ)上加1（如果不理解，在回看一下dp[i][j]的定義）

if (s[i - 1] != t[j - 1])，此時(shí)相當(dāng)于t要?jiǎng)h除元素，t如果把當(dāng)前元素t[j - 1]刪除，那么dp[i][j] 的數(shù)值就是 看s[i - 1]與 t[j - 2]的比較結(jié)果了，即：dp[i][j] = dp[i][j - 1]

class Solution {
    public boolean isSubsequence(String s, String t) {
        int length1 = s.length(); int length2 = t.length();
        int[][] dp = new int[length1+1][length2+1];
        for(int i = 1; i <= length1; i++){
            for(int j = 1; j <= length2; j++){
                if(s.charAt(i-1) == t.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{
                    dp[i][j] = dp[i][j-1];
                }
            }
        }
        if(dp[length1][length2] == length1){
            return true;
        }else{
            return false;
        }
    }
}

?115.不同的子序列：

初始思路&&題解復(fù)盤(pán)：

動(dòng)態(tài)規(guī)劃五部曲;

1)dp[i][j]：以i-1為結(jié)尾的s子序列中出現(xiàn)以j-1為結(jié)尾的t的個(gè)數(shù)為dp[i][j]。

2)確定遞推公式：

• s[i - 1] 與 t[j - 1]相等
• s[i - 1] 與 t[j - 1] 不相等

當(dāng)s[i - 1] 與 t[j - 1]相等時(shí)，dp[i][j]可以有兩部分組成。

1）一部分是用s[i - 1]來(lái)匹配，那么個(gè)數(shù)為dp[i - 1][j - 1]。即不需要考慮當(dāng)前s子串和t子串的最后一位字母，所以只需要 dp[i-1][j-1]。

2）一部分是不用s[i - 1]來(lái)匹配，個(gè)數(shù)為dp[i - 1][j]。

例如： s：baegg 和 t：bag ，s[4] 和 t[2]是相同的，但是字符串s也可以不用s43]來(lái)匹配，即用s[0]s[1]s[3]組成的bag。

當(dāng)然也可以用s[4]來(lái)匹配，即：s[0]s[1]s[4]組成的bag。

當(dāng)s[i - 1] 與 t[j - 1]不相等時(shí)，dp[i][j]只有一部分組成，不用s[i - 1]來(lái)匹配（就是模擬在s中刪除這個(gè)元素），即：dp[i - 1][j]

所以遞推公式為：dp[i][j] = dp[i - 1][j]

3）初始化：

從遞推公式dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; 和 dp[i][j] = dp[i - 1][j]; 中可以看出dp[i][j] 是從上方和左上方推導(dǎo)而來(lái)，如圖：，那么 dp[i][0] 和dp[0][j]是一定要初始化的。

每次當(dāng)初始化的時(shí)候，都要回顧一下dp[i][j]的定義，不要憑感覺(jué)初始化。

dp[i][0]表示什么呢？

dp[i][0] 表示：以i-1為結(jié)尾的s可以隨便刪除元素，出現(xiàn)空字符串的個(gè)數(shù)。

那么dp[i][0]一定都是1，因?yàn)橐簿褪前岩詉-1為結(jié)尾的s，刪除所有元素，出現(xiàn)空字符串的個(gè)數(shù)就是1。

再來(lái)看dp[0][j]，dp[0][j]：空字符串s可以隨便刪除元素，出現(xiàn)以j-1為結(jié)尾的字符串t的個(gè)數(shù)（它都一直是空字符串了，那怎么能有元素咧?。?/span>。

那么dp[0][j]一定都是0，s如論如何也變成不了t。

最后就要看一個(gè)特殊位置了，即：dp[0][0] 應(yīng)該是多少。

dp[0][0]應(yīng)該是1，空字符串s，可以刪除0個(gè)元素，變成空字符串t。

4）遍歷順序

5）舉例：

?

class Solution {
    public int numDistinct(String s, String t) {
        char[] sc = s.toCharArray();
        char[] st = t.toCharArray();
        int[][] dp = new int[sc.length+1][st.length+1];
        for(int i = 0;i<sc.length+1;i++){
            dp[i][0] = 1;
        }
        for(int i = 1;i<sc.length+1;i++){
            for(int j =1;j<st.length+1;j++){
                if(sc[i-1]==st[j-1]){
                    dp[i][j] = dp[i-1][j-1]+dp[i-1][j];
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[sc.length][st.length];

    }
}

?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-788400.html

到了這里，關(guān)于D47|動(dòng)態(tài)規(guī)劃-子序列part2的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！