https://leetcode.cn/problems/distinct-subsequences/submissions/563375885/
这题比较有难度,具体不太好想到,需要以是否选择s[i]来划分子集
这位描述的很清楚,不做过多赘述
class Solution {
public int numDistinct(String s, String t) {
// f[i][j]表示s中前i个字符中选择,有多少个t前j个字符的子串
// 即s前i个字符中有 f[i][j] 个 t前j个字符 的 子序列
// 以s第i个字符和t中第j个字符是否相同划分子集
// 若相同,则意味着 只需要考虑s前i-1个字符中 有多少个 t[0:j-2],即t的前j-1个字符 再加上前面有多少个完整的t,即f[i-1][j]
// 因为这些都可以 和 最后的 s[i] 一起凑成 t
// 若不相同,则不需要考虑s的第i个字符了,而是要考虑s的前i-1个字符
// f[i][j] = if(s[i]==t[j]) f[i-1][j-1]
// else f[i-1][j]
// f[0][0]=1 // 空串里有一个空串
// f[0~n][0]=1,f[0][1]=0
int[][] f=new int[1010][1010];
for(int i=0;i<=s.length();i++)f[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))f[i][j]=f[i-1][j-1]+f[i-1][j];
else f[i][j]=f[i-1][j];
}
}
return f[s.length()][t.length()] % 1000000007;
}
}
标签:int,115,空串,序列,leetcode,个字符 From: https://www.cnblogs.com/lxl-233/p/18406634