The fewest insertions to make a palindrome

def min_insertions(s):
    n = len(s)
    nxt = [0] * n                          # row i + 1 of ins(i, j)
    for i in range(n - 1, -1, -1):
        cur = [0] * n
        for j in range(i + 1, n):
            if s[i] == s[j]:
                cur[j] = nxt[j - 1] if j - 1 >= i + 1 else 0   # ends mirror each other
            else:
                cur[j] = 1 + min(nxt[j], cur[j - 1])           # insert a copy of one end
        nxt = cur
    return nxt[n - 1] if n > 1 else 0

#include <algorithm>
#include <string>
#include <vector>

int solve(std::string s) {
    const int n = s.size();
    std::vector<int> nxt(n, 0), cur(n, 0);
    for (int i = n - 1; i >= 0; --i) {
        std::fill(cur.begin(), cur.end(), 0);
        for (int j = i + 1; j < n; ++j)
            cur[j] = s[i] == s[j] ? (j - 1 >= i + 1 ? nxt[j - 1] : 0) : 1 + std::min(nxt[j], cur[j - 1]);
        std::swap(nxt, cur);
    }
    return n > 1 ? nxt[n - 1] : 0;
}

class Solution {
    public int minInsertions(String s) {
        int n = s.length();
        int[] nxt = new int[n], cur = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            java.util.Arrays.fill(cur, 0);
            for (int j = i + 1; j < n; j++)
                cur[j] = s.charAt(i) == s.charAt(j) ? (j - 1 >= i + 1 ? nxt[j - 1] : 0) : 1 + Math.min(nxt[j], cur[j - 1]);
            int[] t = nxt; nxt = cur; cur = t;
        }
        return n > 1 ? nxt[n - 1] : 0;
    }
}

function minInsertions(s) {
  const n = s.length;
  let nxt = new Array(n).fill(0);
  for (let i = n - 1; i >= 0; i--) {
    const cur = new Array(n).fill(0);
    for (let j = i + 1; j < n; j++)
      cur[j] = s[i] === s[j] ? (j - 1 >= i + 1 ? nxt[j - 1] : 0) : 1 + Math.min(nxt[j], cur[j - 1]);
    nxt = cur;
  }
  return n > 1 ? nxt[n - 1] : 0;
}

fn solve(s: &str) -> i64 {
    let c: Vec<u8> = s.bytes().collect();
    let n = c.len();
    let mut nxt = vec![0i64; n];
    for i in (0..n).rev() {
        let mut cur = vec![0i64; n];
        for j in i + 1..n {
            cur[j] = if c[i] == c[j] {
                if j >= i + 2 { nxt[j - 1] } else { 0 }
            } else {
                1 + nxt[j].min(cur[j - 1])
            };
        }
        nxt = cur;
    }
    if n > 1 { nxt[n - 1] } else { 0 }
}

import Data.Array

solve :: String -> Int
solve s = ins ! (0, n - 1)
  where
    n = length s
    a = listArray (0, n - 1) s
    -- a lazy interval table: each entry reads shorter intervals only
    ins = array ((0, 0), (n - 1, n - 1)) [((i, j), go i j) | i <- [0 .. n - 1], j <- [0 .. n - 1]] :: Array (Int, Int) Int
    go i j
      | i >= j = 0
      | a ! i == a ! j = if i + 1 <= j - 1 then ins ! (i + 1, j - 1) else 0
      | otherwise = 1 + min (ins ! (i + 1, j)) (ins ! (i, j - 1))