leetcode 115. 不同的子序列

r囧r小猫 2022-02-05 12:39 157阅读 0赞

**递归超时 唉**

#include <iostream>
    #include <string>
    #include <vector>
    using namespace std;
    #define debug(x) cout<<#x<<": "<<x<<endl;
    class Solution { 
    public:
        string s,t;
    
        void dispve(vector<int> ve){ 
            for(auto i :ve){ 
                cout<<i<<" ";
            }
            cout<<endl;
        }
        int numDistinct(string s, string t) { 
            this->s = s;
            this->t = t;
            return findw(0,0);
        }
        int findw(int spos,int tpos){ 
            if(s.size()==0){ 
                return 0;
            }else if(tpos >= t.size()){ 
                return 1;
            }
            int p = spos;
            int ans = 0;
            while( ( p = s.find( t[tpos],p ) )!=-1 ){ 
                p++;
                ans += findw(p,tpos+1);
            }
            return ans;
        }
    };
    
    int main()
    { 
        Solution Solution1;
        string a = "adbdadeecadeadeccaeaabdabdbcdabddddabcaaadbabaaedeeddeaeebcdeabcaaaeeaeeabcddcebddebeebedaecccbdcbcedbdaeaedcdebeecdaaedaacadbdccabddaddacdddc";
        string b = "bcddceeeebecbc";
        cout<<Solution1.numDistinct(a,b)<<endl;
        return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0wxNTU4MTk4NzI3_size_16_color_FFFFFF_t_70]  
**dp**

/* 设dp[i][j]表示s[0:i-1]的子序列中t[0:j-1]出现的次数，则 * 1.若s[i-1] == t[j-1] => dp[i][j] = dp[i-1][j-1] (用s[i-1]与t[j-1]配对) * + dp[i-1][j](抛弃s[i-1],不用s[i-1]与t[j-1]配对) * 2.若s[i-1] != t[j-1] => dp[i-1][j] (直接抛弃s[i-1],不用s[i-1]与t[j-1]配对) */
    class Solution { 
    public:
        int numDistinct(string s, string t) { 
            vector< vector<long long> >dp(s.size()+1,vector<long long>(t.size()+1, 0) );
            for(int i = 0;i < s.size();i++){ 
                dp[i][0] = 1;
            }
            //debug(dp.size());
            for(int i=1;i<dp.size();i++){ 
                for(int j=1;j<=i && j<=t.size();j++){ 
                    if(s[i-1] == t[j-1]){ 
                        dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
                    }else{ 
                        dp[i][j] = dp[i-1][j];
                    }
                }
            }
            return dp[s.size()][t.size()];
        }
    };

![在这里插入图片描述][20190505214746470.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0wxNTU4MTk4NzI3_size_16_color_FFFFFF_t_70]: /images/20220205/c1d899f21f294598aa9c317b303eab7c.png
[20190505214746470.png]: /images/20220205/47ff972c37124ca68f35a3c23dddfbd2.png