DynamicProgrammingStriver/DistinctSubsequencesLecture32.cpp at main · dhruvkej9/DynamicProgrammingStriver · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <vector>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
//https://bit.ly/3nZNxy7
int solve1(int i,int j,string &s,string &t,vector<vector<int>> &dp)
{
    if(j == 0) return 1;
    if(i == 0) return 0;
    if(dp[i][j] != -1) return dp[i][j];
    if(s[i-1] == t[j-1])
    {
        return dp[i][j] = (solve1(i-1,j-1,s,t,dp) + solve1(i-1,j,s,t,dp));
    }
    return dp[i][j] = solve1(i-1,j,s,t,dp);
}
int solve2(string &s,string &t)
{
    int n = s.size();
    int m = t.size();
    vector<vector<double>> dp(n+1,vector<double>(m+1,0));
    for(int i = 0;i <= n;i++) dp[i][0] = 1;
    // for(int j = 1;j <= m;j++) dp[0][j] = 0;

    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= m;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 (int)dp[n][m];
}
int solve3(string &s,string &t)
{
    int n = s.size();
    int m = t.size();
    vector<double> prev(m+1,0),cur(m+1,0);
    prev[0] = cur[0] = 1;

    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= m;j++)
        {
            if(s[i-1] == t[j-1])
            {
                cur[j] = prev[j-1] + prev[j];
            }
            else
            {
                cur[j] = prev[j];
            }
        }
        prev = cur;
    }
    return (int)prev[m];
}
int solve4(string &s,string &t)
{
    int n = s.size();
    int m = t.size();
    vector<double> dp(m+1,0);
    dp[0] = 1;
    for(int i = 1;i <= n;i++)
    {
        for(int j = m;j >= 1;j--)
        {
            if(s[i-1] == t[j-1])
            {
                dp[j] += dp[j-1];
            }
        }
    }
    return (int)dp[m];
}

long long numDistinct(string s, string t)
{
    int n = s.size();
    int m = t.size();
    // vector<vector<int>> dp(n+1,vector<int>(m+1,-1));
    // return solve1(n,m,s,t,dp);
    // return solve2(s,t);
    // return solve3(s,t);
    return solve4(s,t);
}