You are viewing a single comment's thread. Return to all comments →
DP in C++ code, simple version
int max_substr(const std::string& s1, const std::string& s2, int pos1, int pos2, std::vector<std::vector<int>>& mem) { if (pos1 == s1.size() || pos2 == s2.size()) { return 0; } if (mem[pos1][pos2] != -1) { return mem[pos1][pos2]; } if (s1[pos1] == s2[pos2]) { mem[pos1][pos2] = 1 + max_substr(s1, s2, pos1 + 1, pos2 + 1, mem); return mem[pos1][pos2]; } mem[pos1][pos2] = std::max(max_substr(s1, s2, pos1, pos2 + 1, mem), max_substr(s1, s2, pos1 + 1, pos2, mem)); return mem[pos1][pos2]; } int commonChild(string s1, string s2) { std::vector<std::vector<int>> mem(s1.size(), std::vector<int>(s2.size(), -1)); return max_substr(s1, s2, 0, 0, mem); }
Seems like cookies are disabled on this browser, please enable them to open this website
Common Child
You are viewing a single comment's thread. Return to all comments →
DP in C++ code, simple version