The fewest cuts into palindromes

def min_cut(s):
    n = len(s)
    pal = [[False] * n for _ in range(n)]     # pal[j][i]: is s[j..i] a palindrome
    cuts = [0] * n                            # cuts[i]: fewest cuts for s[0..i]
    for i in range(n):
        best = i                              # cut between every character
        for j in range(i + 1):
            if s[j] == s[i] and (i - j < 3 or pal[j + 1][i - 1]):
                pal[j][i] = True
                best = 0 if j == 0 else min(best, cuts[j - 1] + 1)
        cuts[i] = best
    return cuts[n - 1]

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

int solve(std::string s) {
    const int n = s.size();
    std::vector<std::vector<bool>> pal(n, std::vector<bool>(n, false));
    std::vector<int> cuts(n, 0);
    for (int i = 0; i < n; ++i) {
        int best = i;
        for (int j = 0; j <= i; ++j)
            if (s[j] == s[i] && (i - j < 3 || pal[j + 1][i - 1])) {
                pal[j][i] = true;                         // s[j..i] is a palindrome
                best = j == 0 ? 0 : std::min(best, cuts[j - 1] + 1);
            }
        cuts[i] = best;
    }
    return cuts[n - 1];
}

class Solution {
    public int minCut(String s) {
        int n = s.length();
        boolean[][] pal = new boolean[n][n];
        int[] cuts = new int[n];
        for (int i = 0; i < n; i++) {
            int best = i;
            for (int j = 0; j <= i; j++)
                if (s.charAt(j) == s.charAt(i) && (i - j < 3 || pal[j + 1][i - 1])) {
                    pal[j][i] = true;                     // s[j..i] is a palindrome
                    best = j == 0 ? 0 : Math.min(best, cuts[j - 1] + 1);
                }
            cuts[i] = best;
        }
        return cuts[n - 1];
    }
}

function minCut(s) {
  const n = s.length;
  const pal = Array.from({ length: n }, () => new Array(n).fill(false));
  const cuts = new Array(n).fill(0);
  for (let i = 0; i < n; i++) {
    let best = i;
    for (let j = 0; j <= i; j++) {
      if (s[j] === s[i] && (i - j < 3 || pal[j + 1][i - 1])) {
        pal[j][i] = true;                     // s[j..i] is a palindrome
        best = j === 0 ? 0 : Math.min(best, cuts[j - 1] + 1);
      }
    }
    cuts[i] = best;
  }
  return cuts[n - 1];
}

fn solve(s: &str) -> i64 {
    let c: Vec<u8> = s.bytes().collect();
    let n = c.len();
    let mut pal = vec![vec![false; n]; n];
    let mut cuts = vec![0i64; n];
    for i in 0..n {
        let mut best = i as i64;
        for j in 0..=i {
            if c[j] == c[i] && (i - j < 3 || pal[j + 1][i - 1]) {
                pal[j][i] = true;                         // s[j..i] is a palindrome
                best = if j == 0 { 0 } else { best.min(cuts[j - 1] + 1) };
            }
        }
        cuts[i] = best;
    }
    cuts[n - 1]
}

import Data.Array

solve :: String -> Int
solve s = cuts ! (n - 1)
  where
    n = length s
    a = listArray (0, n - 1) s
    -- lazy tables: pal ! (j, i) and cuts ! i refer only to entries already defined in terms of smaller ones
    pal = array ((0, 0), (n - 1, n - 1)) [((j, i), j <= i && a ! j == a ! i && (i - j < 3 || pal ! (j + 1, i - 1))) | j <- [0 .. n - 1], i <- [0 .. n - 1]] :: Array (Int, Int) Bool
    cuts = listArray (0, n - 1) [best i | i <- [0 .. n - 1]] :: Array Int Int
    best i
      | pal ! (0, i) = 0
      | otherwise = minimum [cuts ! (j - 1) + 1 | j <- [1 .. i], pal ! (j, i)]