不同子序列--动态规划完成

题目描述：

       给定两个字符串S和T，求S有多少个不同的子串与T相同。S的子串定义为在S中任意去掉0个或者多个字符形成的串。子串可以不连续，但是相对位置不能变。比如“ACE”是“ABCDE”的子串，但是“AEC”不是。

       解题思路：

       假设S字符串为“rabbbit”，T字符串为“rabbit”，行为S字符串中取前 i 个字符，列为T字符串中取前 j 个字符，矩阵值为包含几种情况，列完所有的情况之后，就会发现，如果S的当前值与T的当前值相同。

       以列表（4,3）位置的值为例子。S的第4个字符与T的第三个字符‘b’相同，这个时候（4,3）位置的值就是（3,3）位置加上（（3,2）+ ‘b’）的值的和。 

       解释：S的前4个字符中的前三个包含T的前三个字符是已知，但是此时S的第四个字符与T的第三个字符也相同，这个时候就看在S的前三个字符中包含有T的前两个字符的所有情况，发现是有值的，此时使用S的前两个字符与S的第四个字符相组合成的字符串与T的前三个字符所组成的字符串相同，所以又有一种新的情况出现。（当S后面取到的字符与T的最后一个字符相同时有同样的道理，如果字符不相同则不用考虑这一步，直接是沿用上一行所取得的对应值）

       代码如下：

public class Solution {
    public int numDistinct(String S, String T) {
        int len1 = S.length();
        int len2 = T.length();
        if(len1 == 0) {
            if(len2 == 0) {
                return 1;    //都为空时，返回1
            }
            return 0;    //T为空返回0
        }
        int[][] mat = new int[len1 + 1][len2 + 1];    //多申请一位，因为从1开始寻找
        for(int i = 0;i < len2 + 1;i++) {    //第一行全为0
            mat[0][i] = 0;
        }
        for(int i = 0;i < len1 + 1;i++) {    //第一列全为1
            mat[i][0] = 1;
        }
        for(int i = 1;i <= len1;i++) {
            for(int j = 1;j <= len2;j++) {
                if(S.charAt(i - 1) == T.charAt(j - 1)) {    //如果首尾字母相同
                    mat[i][j] = mat[i - 1][j] + mat[i - 1][j - 1];    //不包含这个新字母+包含这个新字母
                }else {
                    mat[i][j] = mat[i - 1][j];    //不相同直接返回不包含这个新字母的值
                }
            }
        }
        return mat[len1][len2];
    }
}
           

       仔细的观察代码之后会发现，每次更新新的信息时，只会用到上一行的值，而与其他的值无关，这时候能否将一个矩阵优化为一个空间更小的数组呢？答案是肯定的，这时候观察代码，发现更新第（i，j）个值的时候，需要用到的值为（i - 1,j）（i -1,j -1）而这个时候，如果先更新排在前面的值，就会影响到后面值的变化，所以不能从头来更新，这时候就需要从尾部来更新，就能保证数值的正确性。

       优化空间之后的代码：

public class Solution {
    public int numDistinct(String S, String T) {
        int len1 = S.length();
        int len2 = T.length();
        if(len1 == 0) {
            if(len2 == 0) {
                return 1;
            }
            return 0;
        }
        if(len2 == 0) {
            return 1;
        }
        int[] mat = new int[len2 + 1];
        mat[0] = 1;
        for(int i = 1;i <= len1;i++) {
            for(int j = len2;j >= 1;j--) {    //从尾部来更新这个数组
                if(S.charAt(i - 1) == T.charAt(j - 1)) {
                    mat[j] = mat[j] + mat[j - 1];    //相同的时候更新，不相同就不改变这个值
                }
            }
        }
        return mat[len2];
    }
}