动态规划—distinct-subsequences

题目：

Given a string S and a string T, count the number of distinct subsequences of T in S.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie,"ACE"is a subsequence of"ABCDE"while"AEC"is not).

Here is an example:
S ="rabbbit", T ="rabbit"

Return3.

思路：

1. 初始化一个矩阵number[i][j]用来记录字符串T的前j个字符出现在字符串S的前i个字符的次数，当j=0时，令number[i][j]=1；

2. 当S的第i个字符与T的第j个字符不同时，则说明S的第i个字符对number[i][j]没有影响，即number[i][j]=number[i-1][j]；

3. 当S的第i个字符与T的第j个字符不同时，则说明S的第i个字符对number[i][j]有影响，number[i][j]除了要算上原来的number[i-1][j]，还要算上新的可能性，即number[i-1][j-1].

例子

	0	r	a	b	b	i	t
0	1	0	0	0	0	0	0
r	1	1	0	0	0	0	0
a	1	1	1	0	0	0	0
b	1	1	1	1	0	0	0
b	1	1	1	2	1	0	0
b	1	1	1	3	3	0	0
i	1	1	1	3	3	3	0
t	1	1	1	3	3	3	3

代码：

     public static int result(String str1, String str2){

         int len1 = str1.length(), len2 = str2.length();

         int[][] res = new int[len1+1][len2+1];

         for(int i=0;i<len1+1;i++){

             res[i][0] = 1;

         }

         for(int i=1;i<len1+1;i++){

             for(int j=1;j<len2+1;j++){

                 if(str1.charAt(i-1)!=str2.charAt(j-1))

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

                 else

                     res[i][j] = res[i-1][j]+res[i-1][j-1];

             }

         }

         return res[len1][len2];

     }

巴特西

动态规划—distinct-subsequences

最新文章

热门文章

	0	r	a	b	b	i	t
0	1	0	0	0	0	0	0
r	1	1	0	0	0	0	0
a	1	1	1	0	0	0	0
b	1	1	1	1	0	0	0
b	1	1	1	2	1	0	0
b	1	1	1	3	3	0	0
i	1	1	1	3	3	3	0
t	1	1	1	3	3	3	3

	0	r	a	b	b	i	t
0	1	0	0	0	0	0	0
r	1	1	0	0	0	0	0
a	1	1	1	0	0	0	0
b	1	1	1	1	0	0	0
b	1	1	1	2	1	0	0
b	1	1	1	3	3	0	0
i	1	1	1	3	3	3	0
t	1	1	1	3	3	3	3

	0	r	a	b	b	i	t
0	1	0	0	0	0	0	0
r	1	1	0	0	0	0	0
a	1	1	1	0	0	0	0
b	1	1	1	1	0	0	0
b	1	1	1	2	1	0	0
b	1	1	1	3	3	0	0
i	1	1	1	3	3	3	0
t	1	1	1	3	3	3	3