C++ || recursive || memoization || easy to understand
\nclass Solution {\npublic:\n    \n    map <pair<int,int>, int> dp;\n    \n    int same(string s, string t, int i, int j) {\n        \n        if(i < 0 or j < 0
```\nclass Solution {\npublic:\n    \n    map <pair<int,int>, int> dp;\n    \n    int same(string s, string t, int i, int j) {\n        \n        if(i < 0 or j < 0) {\n            \n            return 0;\n        }\n        \n        if(s[i] == t[j]) {\n            \n            return 1 + same(s, t, i - 1, j - 1);\n        }\n        else {\n            return 0;\n        }\n    }\n    \n    int calc(string s, string t, int i, int j) {\n                \n        if(i < 0 or j < 0 or i >= s.length() or j >= t.length()) {\n            return 0;\n        }\n        else if(dp.find({i, j}) != dp.end()) {\n            \n            return dp[{i, j}];\n        }\n        \n        int ans = 0;\n        \n        if(s[i] == t[j]) {\n            \n            ans = calc(s, t, i - 1, j - 1);\n        }\n        else {\n            \n            ans = 1 + same(s, t, i - 1, j - 1);\n            \n        }\n        \n        return dp[{i, j}] = ans;\n    }\n    \n    int countSubstrings(string s, string t) {\n        \n        int ans = 0;\n        \n        for(int i = 0 ; i < s.length(); i++) {\n            \n            for(int j = 0 ; j < t.length(); j++) {\n                \n                ans += calc(s, t, i, j);\n            }\n        }\n        \n        return ans;\n    }\n};\n```
['Recursion', 'Memoization', 'C']