Very Easy DP Solution | C++ & Java | Fast & Explained
Solution\n- Use Dynamic Programming technique to try all possible ways to make the string palindrome.\n- The dp array is a 2D array, where dp[l][r] is the minim
# Solution\n- Use `Dynamic Programming` technique to try all possible ways to make the string palindrome.\n- The `dp` array is a 2D array, where `dp[l][r]` is the minimum number of insertions needed to make the substring `s[l..r]` a palindrome.\n- If `s[l] == s[r]`, then you can move the 2 pointers to the inside and calculate the minimum number of insertions needed for the substring `s[l + 1..r - 1]`.\n- If `s[l] != s[r]`, then try the 2 options to move `l` to the right or `r` to the left.\n- For all the combinations return the minimum number needed to convert the string to a palindrome one.\n# Complexity\n- Time Complexity: `O(N ^ 2)`, where `N` is the length of the string.\n- Space Complexity: `O(N ^ 2)`, for the `dp` array.\n\n# Code\n## C++\n```cpp\nclass Solution {\npublic:\n    int dp[505][505];\n\n    int solve(string &s, int l, int r) {\n        if(l >= r) return 0;\n\n        auto & ret = dp[l][r];\n        if(~ret) return ret;\n\n        if(s[l] == s[r]) ret = solve(s, l + 1, r - 1);\n        else ret = 1 + min(solve(s, l + 1, r), solve(s, l, r - 1));\n        return ret;\n    }\n\n    int minInsertions(string s) {\n        memset(dp, -1, sizeof dp);\n        return solve(s, 0, (int) s.size() - 1);\n    }\n};\n```\n\n## Java\n```java\nclass Solution {\n    int [][] dp = new int[505][505];\n\n    int solve(String s, int l, int r) {\n        if(l >= r) return 0;\n        if(dp[l][r] != -1) return dp[l][r];\n        if(s.charAt(l) == s.charAt(r)) return dp[l][r] = solve(s, l + 1, r - 1);\n        return dp[l][r] = 1 + Math.min(solve(s, l + 1, r), solve(s, l, r - 1));\n    }\n\n    public int minInsertions(String s) {\n        for (int i = 0; i < 505; i++) {\n            for (int j = 0; j < 505; j++) {\n                dp[i][j] = -1;\n            }\n        }\n        return solve(s, 0, s.length() - 1);\n    }\n}\n```
['C', 'Java']