Update 115.Distinct-Subsequences.cpp

wisdompeak · web-flow · commit 84e4d1f98974 · 2021-09-19T01:37:52.000-07:00
diff --git a/Dynamic_Programming/115.Distinct-Subsequences/115.Distinct-Subsequences.cpp b/Dynamic_Programming/115.Distinct-Subsequences/115.Distinct-Subsequences.cpp
@@ -4,20 +4,27 @@ class Solution {
     {
         int m = s.size();
         int n = t.size();
-        auto dp = vector<vector<long>>(m+1,vector<long>(n+1,0));
+        auto dp = vector<vector<long long>>(m+1,vector<long long>(n+1,0));
         s = "#"+s;
         t = "#"+t;
+                
+        if (m<n) 
+            return 0;
+        if (m==n)
+            return (s==t);
         
-        for (int i=0; i<=m; i++) dp[i][0] = 1;
+        for (int i=0; i<=m; i++)
+            dp[i][0] = 1;
         
         for (int i=1; i<=m; i++)
             for (int j=1; j<=n; j++)
             {
                 if (s[i]==t[j])
-                    dp[i][j] += dp[i-1][j-1];
-                dp[i][j] += dp[i-1][j];
+                    dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
+                else
+                    dp[i][j] = dp[i-1][j];
+                //cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
             }
-        
         return dp[m][n];
     }
 };
