a*e
1 楼
https://oj.leetcode.com/problems/distinct-subsequences/
DP的题在现场除了写出来，还要求优化space吗？像这个要改成一维的table吗？
class Solution {
public:
int numDistinct(string S, string T) {
int slen=S.length(), tlen=T.length();
if (slen
vector> t(slen+1,vector((tlen+1), 0));
for(int i=0; i<=slen; i++)
t[i][0]=1;
for (int i=1; i<=slen; i++)
for (int j=1; j<=tlen; j++)
{
if (S[i-1]==T[j-1])
t[i][j]=t[i-1][j]+t[i-1][j-1];
else
t[i][j]=t[i-1][j];
}
return t[slen][tlen];
}
};
开始写的TLE了，
class Solution {
public:
int numDistinct(string S, string T) {
int slen=S.length(), tlen=T.length();
if (slen
int num=0, startIdx=0, startjIdx=0;
helper(S,T,num,startIdx,startjIdx);
return num;
}
void helper(string S, string T, int &num, int startIdx, int startjIdx)
{
if (startjIdx==T.length())
{
num++;
return;
}
for (int i=startIdx; i
if (S[i]==T[j])
helper(S,T,num, i+1, j+1);
}
}
};
DP的题在现场除了写出来，还要求优化space吗？像这个要改成一维的table吗？
class Solution {
public:
int numDistinct(string S, string T) {
int slen=S.length(), tlen=T.length();
if (slen
vector
for(int i=0; i<=slen; i++)
t[i][0]=1;
for (int i=1; i<=slen; i++)
for (int j=1; j<=tlen; j++)
{
if (S[i-1]==T[j-1])
t[i][j]=t[i-1][j]+t[i-1][j-1];
else
t[i][j]=t[i-1][j];
}
return t[slen][tlen];
}
};
开始写的TLE了，
class Solution {
public:
int numDistinct(string S, string T) {
int slen=S.length(), tlen=T.length();
if (slen
int num=0, startIdx=0, startjIdx=0;
helper(S,T,num,startIdx,startjIdx);
return num;
}
void helper(string S, string T, int &num, int startIdx, int startjIdx)
{
if (startjIdx==T.length())
{
num++;
return;
}
for (int i=startIdx; i
if (S[i]==T[j])
helper(S,T,num, i+1, j+1);
}
}
};
