正文
leetcode distinct-subsequences(DP)
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
参考https://oj.leetcode.com/problems/distinct-subsequences
动态规划方程
dp[i][j]=dp[i-1][j-1]+dp[i-1][j] (s(i)==t(i))
dp[i][j]=dp[i-1][j];
边界条件： iif(j==0) d[i][j]=1;
自己画个矩阵看看。
可能出错，
1.直接递归超时
public class Solution {
public int numDistinct(String S, String T) {
int len1=S.length();
int len2=T.length();
if(len1<len2) return 0;
int ans=dp(S,T,len1,len2);
return ans;
}
public int dp(String S,String T,int i,int j)
{
if(i<j) return 0;
if(i==0&&j==0) return 1; // "" ""
if(j==0&&i!=0) return 0;//"xxxx" ""
if(S.charAt(i-1)==T.charAt(j-1))
{
return dp(S,T,i-1,j-1)+dp(S,T,i-1,j);
}
else return dp(S,T,i-1,j);
}
}
2、加入一个矩阵，依然超时
public class Solution {
public int numDistinct(String S, String T) {
int len1=S.length();
int len2=T.length();
if(len1<len2) return 0;
int d[][]=new int[len1+1][len2+1];
int ans=dp(S,T,len1,len2,d);
return ans;
}
public int dp(String S,String T,int i,int j,int d[][])
{
if(i<j) return 0;
if(i==0&&j==0) return 1; // "" ""
if(i!=0&&j==0) return 0;
if(d[i][j]!=0) return d[i][j];
if(S.charAt(i-1)==T.charAt(j-1))
{
d[i-1][j-1]=dp(S,T,i-1,j-1,d);
d[i-1][j]=dp(S,T,i-1,j,d);
return d[i-1][j-1]+d[i-1][j];
}
else
{
d[i-1][j]=dp(S,T,i-1,j,d);
return d[i-1][j];
}
}
}
3.真正的动态规划
public class Solution {
public int numDistinct(String S, String T) {
int len1=S.length();
int len2=T.length();
if(len1<len2) return 0;
int d[][]=new int[len1+1][len2+1];
for(int i=0;i<=len1;i++)
{
d[i][0]=1;
}
for(int i=1;i<=len1;i++)
{
for(int j=1;j<=len2&&j<=i;j++)
{
if(S.charAt(i-1)==T.charAt(j-1))
{
d[i][j]=d[i-1][j-1]+d[i-1][j];
}
else
{
d[i][j]=d[i-1][j];
}
}
}
return d[len1][len2];
}
}
