leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0115.cpp (609B)

      1 class Solution {
      2     static int dp[1001][1001];
      3 
      4     static int rec(const string &s, const string &t, int check, int goal) {
      5         if (goal == size(t)) return 1;
      6         if (check == size(s)) return 0;
      7         if (dp[check][goal] != -1) return dp[check][goal];
      8 
      9         int res = rec(s, t, check + 1, goal);
     10         if (s[check] == t[goal]) res += rec(s, t, check + 1, goal + 1);
     11         return dp[check][goal] = res;
     12     }
     13 
     14   public:
     15     int numDistinct(const string &s, const string &t) const {
     16         memset(dp, 0xFF, sizeof(dp));
     17         return rec(s, t, 0, 0);
     18     }
     19 };
     20 
     21 int Solution::dp[1001][1001];