leetcode 115. 不同的子序列

快来打我* 2023-07-03 04:42 36阅读 0赞

设dp\[i\]\[j\]表示s的前i个字符中，含有t的前j个字符的序列个数。

首先先明确一点。当t为空串时，dp\[i\]\[0\]=1。即空串有一种选法。

当s\[i\]==t\[j\]时，dp\[i\]\[j\]+=dp\[i-1\]\[j-1\] 。此时还需要向前遍历，寻找s\[k\]==t\[j\]

否则dp\[i\]\[j\]=dp\[i-1\]\[j\]。

复杂度 m\*m\*n

class Solution {
    public:
        int numDistinct(string s, string t) {
            int m=s.size();
            int n=t.size();
            long long dp[m+3][n+3];
            memset(dp,0,sizeof(dp));
            dp[0][0]=1;
            for(int i=1;i<=m;i++)
            {
                dp[i][0]=1;
            }
            for(int j=1;j<=n;j++)
            {
                for(int i=1;i<=m;i++)
                {
                    if(s[i-1]==t[j-1])
                    {
                        dp[i][j]+=dp[i-1][j-1];
                        for(int k=i-1;k>=j;k--)
                        {
                            if(s[k-1]==t[j-1])
                            {
                                dp[i][j]+=dp[k-1][j-1];
                            }
                        }
                    }
                    else
                    {
                        dp[i][j]=dp[i-1][j];
                    }
                    //cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
                }
            }
            return dp[m][n];
        }
    };

优化：其实向前搜索的过程，就是dp\[i-1\]\[j\]。

所以复杂度可以到m\*n

class Solution {
    public:
        int numDistinct(string s, string t) {
            int m=s.size();
            int n=t.size();
            long long dp[m+3][n+3];
            memset(dp,0,sizeof(dp));
            dp[0][0]=1;
            for(int i=1;i<=m;i++)
            {
                dp[i][0]=1;
            }
            for(int j=1;j<=n;j++)
            {
                for(int i=1;i<=m;i++)
                {
                    if(s[i-1]==t[j-1])
                    {
                        dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
                        // for(int k=i-1;k>=j;k--)
                        // {
                        //     if(s[k-1]==t[j-1])
                        //     {
                        //         dp[i][j]+=dp[k-1][j-1];
                        //     }
                        // }
                    }
                    else
                    {
                        dp[i][j]=dp[i-1][j];
                    }
                    //cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
                }
            }
            return dp[m][n];
        }
    };