Day 54 | 392. 判断子序列 & 115. 不同的子序列

392. 判断子序列 

动态规划解题思路：    

①确定dp数组以及下标含义

        dp[i][j]：以下标i-1结尾的字符串s与下标j-1结尾的字符串t中相同子序列长度为dp[i][j]

②确定递推公式

        每次遍历比较s[i]与t[j]的值。

        若相等:                                

                                                       dp[i][j]=dp[i-1][j-1]+1

        若不相同，则相当于忽视长字符串中遍历的当前元素,用长字符串上一个元素匹配结果:

                                                       dp[i][j]=dp[i][j-1];

③dp数组如何初始化

        dp长度为数组长度+1。

        为了方便计算，dp[i][0]和dp[0][j]都初始化为0，相当于与空字符串的相同子序列长度为0。

④确定遍历顺序

          从前向后遍历。

⑤举例推导dp数组

115. 不同的子序列

动态规划解题思路：    

①确定dp数组以及下标含义

        dp[i][j]：以下标i-1结尾的字符串s与下标j-1结尾的字符串t中相同子序列个数为dp[i][j]

②确定递推公式

        每次遍历比较s[i-1]与t[j-1]的值。

        若相等，有两种选择，匹配或不匹配（可以让其他的元素匹配）                               

                                                  dp[i][j]=dp[i-1][j-1]+dp[i-1][j]

        若不相同，则不匹配,则返回长字符串前一个元素匹配短字符串的结果。

                                                       dp[i][j]=dp[i-1][j];

③dp数组如何初始化

        当长短字符串为空时，可以匹配，dp[0][0]=1;

        长字符串为空，短字符串非空，不能匹配 dp[0][j]=0;

        短字符串为空，长字符串非空，不能匹配 dp[i][0]=1;

④确定遍历顺序

          从前向后，从上至下遍历。

⑤举例推导dp数组

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