题解 | #最长公共子序列-II#

关键是要在动态规划的过程中如果不相等的时候要保存那个最大的。然后基于此原理得到的dp，然后在倒着遍历，知道对应的元素相同添加上就行了。注意空值处理。

class Solution {
public:
    /**
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    string LCS(string s1, string s2) {
        // write code here

        string result;

        int f[s1.length()+1][s2.length()+1];

        for(int i = 0;i<= s1.length();i++){
            f[i][0] = 0;
        }

        for(int j = 0;j<= s2.length();j++){
            f[0][j] = 0;
        }

        for(int i = 1; i <=s1.length();i++){
           for(int j = 1; j<=s2.length();j++){
               if(s1[i-1] == s2[j-1]){
                   f[i][j] = f[i-1][j-1] +1;
               }else{
                   f[i][j] = max(f[i][j-1],f[i-1][j]);
               }
           }
        }


        int i = s1.length(), j = s2.length();
        while(i>0&&j>0){
            if(s1[i-1]==s2[j-1]){
                result+=s1[i-1];
                i--;
                j--;
            }else{
                if(f[i][j-1]>f[i-1][j]){
                    j--;
                }else if(f[i][j-1]< f[i-1][j]){
                    i--;
                }else{
                    i--;
                }
            }
        }

        if(result.length()==0){
            return "-1";
        }

        reverse(result.begin(),result.end());

        return result;

    }
};