Solution using dp
Intuition\nTo solve this problem, we can use dynamic programming (DP). We define dp[i][j] as the minimum number of insertions needed to make the substring s[i..
# Intuition\nTo solve this problem, we can use dynamic programming (DP). We define dp[i][j] as the minimum number of insertions needed to make the substring s[i...j] a palindrome.\n\n# Approach\nWe can observe that if the characters s[i] and s[j] are the same, then we don\'t need to do anything and we can just consider the substring s[i+1...j-1]. Otherwise, we have two options:\n\n1. Insert the character s[j] at the end of the substring s[i...j-1], and consider the substring s[i...j-2] for the next step.\n2. Insert the character s[i] at the beginning of the substring s[i+1...j], and consider the substring s[i+1...j-1] for the next step.\nWe can compute the dp values using bottom-up DP. The base case is when i=j, which means that the substring is already a palindrome and we don\'t need any insertions.\n\n\n\n# Code\n```\nclass Solution {\npublic:\n    int minInsertions(string s) {\n        int n = s.length();\n        vector<vector<int>> dp(n, vector<int>(n, 0));\n        for (int len = 2; len <= n; len++) {\n            for (int i = 0; i < n - len + 1; i++) {\n                int j = i + len - 1;\n                if (s[i] == s[j]) {\n                    dp[i][j] = dp[i+1][j-1];\n                } else {\n                    dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1;\n                }\n            }\n        }\n        return dp[0][n-1];\n    }\n};\n\n```
['String', 'Dynamic Programming', 'C++', 'Java']