1312. Minimum Insertion Steps to Make a String Palindrome ​

int minInsertions(string s) {
    string s2 = s;
    reverse(s2.begin(), s2.end());
    return s.size() - lcs(s, s2);
}

int lcs(string s1, string s2) {
    vector<vector<int>> dp(s1.size()+1, vector<int>(s2.size()+1, 0));
    for(int i = 0; i < s1.size(); i++) {
        for(int j = 0; j < s2.size(); j++) {
            dp[i+1][j+1] = s1[i] == s2[j] ? dp[i][j] + 1 : max(dp[i][j+1], dp[i+1][j]);
        }
    }
    return dp[s1.size()][s2.size()];
}