= longest palindrome subsequence
I know there are a lot of BIG GOD\'s discussions to show how to solve this. \nBut for easy understanding, this problem could be transformed to:\nFinding "longes
I know there are a lot of BIG GOD\'s discussions to show how to solve this. \nBut for easy understanding, this problem could be transformed to:\n**Finding "longest palindrome subsequence", **\nthen transformed to:\n**Finding "longest common subsequence to his reversed string ".**\n```\ninInsertions(String s) \n= n - longthPalSubSeq(s)\n= n - longthCommonSubSeq(s, reversed(s)) \n```\n\n\n```\nclass Solution {\n    //same as find the longest sub palindrome subsequence\n    public int minInsertions(String s) {\n        int n = s.length();\n        int[][] dp = new int[n+1][n+1];\n        for(int i = 0; i < n; i++){\n            for(int j = 0; j < n; j++){\n                if (s.charAt(i) == s.charAt(n - 1 - j)){\n                    dp[i+1][j+1] = dp[i][j] + 1;\n                } else {\n                    dp[i+1][j+1] = Math.max(dp[i+1][j], dp[i][j+1]);\n                }\n            }\n        }\n        return n - dp[n][n];\n    }\n}\n```\n\n\n
[]