class Solution {
  public:
    string LCS(string str1, string str2) {
        vector<vector<unsigned short>> dp;
        unsigned short record = 0;
        int end_pos;
        for (int i = 0; i <= str1.size(); ++i)
            dp.push_back(vector<unsigned short>(str2.size() + 1));
        for (int i = 1; i <= str1.size(); ++i) {
            for (int j = 1; j <= str2.size(); ++j) {
                if (str1[i - 1] == str2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    if (dp[i][j] > record) {
                        record = dp[i][j];
                        end_pos = i;
                    }
                }
            }
        }
        return str1.substr(end_pos - record, record);
    }
};
DP数组定义为：以str[i-1] str[j-1]为结尾的字串的长度
同时需要记录一个全局最长答案，以及此答案对应的字母串的字母下标。我们最后是需要通过这个信息去返回字符串本身的。

PS：
1. 这里因为字符串长度5000以内，因此用unsigned short降低内存占用
2. substr方法注意是（pos，count），而不是（pos，end）。这里跟Python完全不同。