LeetCode115. 不同的子序列

思路

1.dp数组的定义

因为又是一个子字符串问题，所以dp[i][j]定位为s在下标为i-1的位置和t在下标为j-1的位置处，共同拥有的最大公共子序列为dp[i][j].

2.递推公式

要根据s中的第i-1个元素和t中的第j-1个元素是否相等，如果相等则

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

这里为什么是加呢？

因为dp[i][j]可以由两部分组成：一部分是将下标为i-1和j-1的字符去除后的个数；一部分是将s中下标为i-1的字符除去后的个数。

可以理解为去除s中的字符，就是这种情况：t为rabb，s为rab。当i为3，j为2时的情况。

如果不相等就是dp[i][j] = dp[i-1][j];就是将s中下标为i-1的元素剔除后的字符串中有多少个符合条件的t的子字符。 

3.初始化dp数组

根据dp数组的定义，可以知道dp[0][j]全是0；因为是从s中与t相同的子序列。

dp[i][0] = 1;因为以i-1结尾的字符串s中肯定存在一个空的字符串。或者说是以s-1结尾的字符串可以随便删除元素。

4.遍历顺序

根据递推公式可以知道是正序遍历。

5.打印dp数组

dp数组的最后一个元素就是最后的结果。

代码

class Solution {    public int numDistinct(String s, String t) { int l1 = s.length(); int l2 = t.length(); int dp[][] = new int[l1+1][l2+1]; for(int j = 0;j <= l1;j++){     dp[j][0] = 1; } for(int i =1;i<=l1;i++){     for(int j = 1;j<=l2;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[l1][l2];    }}