Algorithm (Dynamic Programming)

1. Let $f(i,j)$ denote the minimum insertion needed to make $S_{i:j}$ a palindrome.
2. Then we have $$f(i,j)=\begin{cases} 0 & \text{if }i=j\\\\ 1 & \text{if }i+1=j\text{ and }S_{i}\neq S_{j}\\\\ 0 & \text{if }i+1=j\text{ and }S_{i}=S_{j}\\\\ f(i+1,j-1) & \text{if }i+1<j\text{ and }S_{i}=S_{j}\\\\ \min\{f(i+1,j),f(i,j-1)\} & \text{if }i+1<j\text{ and }S_{i}\neq S_{j} \end{cases}.$$

Code

template <class F>
struct recursive {
  F f;
  template <class... Ts>
  decltype(auto) operator()(Ts&&... ts)  const { return f(std::ref(*this), std::forward<Ts>(ts)...); }

  template <class... Ts>
  decltype(auto) operator()(Ts&&... ts)  { return f(std::ref(*this), std::forward<Ts>(ts)...); }
};

template <class F> recursive(F) -> recursive<F>;
auto const rec = [](auto f){ return recursive{std::move(f)}; };

class Solution {
 public:
  int minInsertions(string s) {

    const int n = size(s);

    const struct {
      mutable std::optional<int> f[500][500];
    } memo;

    auto f = rec([&, memo = std::ref(memo.f)](auto&& f, int i, int j) -> int {
      if (memo[i][j])
        return memo[i][j].value();
      else
        return *(memo[i][j] = [&] {
          if (i == j)
            return 0;
          else if (i + 1 == j)
            return s[i] == s[j] ? 0 : 1;
          else if (j - i >= 2 and s[i] == s[j])
            return f(i + 1, j - 1);
          else if (j - i >= 2 and s[i] != s[j])
            return std::min(f(i, j - 1) + 1, f(i + 1, j) + 1);
          else throw std::domain_error("unmatched case");
        }());
    });

    return f(0, n - 1);
  }
};