[JAVA] Simple DP with explanation and very small code
The initution is two pointers (at the beginning and at the end end).\n2. Match the the pointer if the match move the pointers(begin+1 and end-1)\n3. If they don
1. The initution is two pointers (at the beginning and at the end end).\n2. Match the the pointer if the match move the pointers(begin+1 and end-1)\n3. If they dont match either you add character at the end or character at the begin. \n4. Since we have a choice here if have to make the min of the two cases. Thus forming a recursive problem.\n5. Since we will be coming across same begin,end pointer pairs we apply DP.\nThis guarantee min solution as we try to explore all the possible cases\n6. O(n^2 \n\n```\nclass Solution {\n    \n    Integer[][] dp;\n    \n    public int helper(int i, int j, String s){\n        \n        if(i>j)\n            return 0;\n        \n        if(dp[i][j] != null)\n            return dp[i][j];\n        int val;\n        \n        if(s.charAt(i) == s.charAt(j))\n            val = helper(i+1,j-1,s);\n        else\n            val = Math.min(helper(i+1,j,s),helper(i,j-1,s)) + 1;\n        \n        dp[i][j] = val;\n        \n        return dp[i][j];\n    }\n    public int minInsertions(String s) {\n        dp = new Integer[s.length()][s.length()];\n        return helper(0,s.length()-1,s);\n    }\n}\n```
[]