# 1312. Minimum Insertion Steps to Make a String Palindrome
###### tags: `Leetcode` `Hard` `Dynamic Programming` `LCS`
Link: https://leetcode.com/problems/minimum-insertion-steps-to-make-a-string-palindrome/
## 思路
如果两个字串是对方的逆序 他们俩又相等 说明这个字串是palindrome
所以本题的答案等同于求这两个字符串的shortest common supersequence (SCS)
## Code

class Solution {
    public int minInsertions(String s) {
        StringBuilder t = new StringBuilder(s);
        t = t.reverse();
        int n = s.length();
        int[][] dp = new int[n+1][n+1];
        for(int i=0; i<=n; i++){
            dp[i][0] = i;
            dp[0][i] = i;
        }
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(s.charAt(i-1)==t.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1]+1;
                }
                else{
                    dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1])+1;
                }
            }
        }
        return dp[n][n]-n;
    }
}