--- a/dynprog.cc	Mon Apr 03 22:46:24 2023 +0200
+++ b/dynprog.cc	Tue Apr 04 22:11:01 2023 +0200
@@ -402,6 +402,51 @@
     return 0;
 }
 
+template<typename It> requires random_access_iterator<It>
+bool is_palindrome(It begin, It end) {
+    const size_t s = end - begin;
+    for (size_t i = 0; i < s/2; i++) {
+        if (*(begin+i) != *(begin + (s-i-1)))
+            return false;
+    }
+    return true;
+}
+
+// https://www.techiedelight.com/find-minimum-cuts-needed-palindromic-partition-string/
+template<typename T, typename R> requires range<R> && is_same_v<range_value_t<R>, T> && random_access_iterator<iterator_t<R>>
+int minimum_palindrome_cuts(const R& range, size_t from, size_t to, unordered_map<pair<size_t, size_t>, int, PairHash>& memo) {
+    if (is_palindrome(range.begin()+from, range.begin()+to))
+        return 0;
+    if (to - from == 1)
+        return 0;
+
+    auto key = make_pair(from, to);
+    auto entry = memo.find(key);
+    if (entry != memo.end())
+        return entry->second;
+
+    int mincuts = to-from;
+    size_t minix = to;
+    for (size_t i = from+1; i < to; i++) {
+        // Split at i.
+        int cuts1 = minimum_palindrome_cuts<T>(range, from, i, memo);
+        int cuts2 = minimum_palindrome_cuts<T>(range, i, to, memo);
+        int cuts = 1 + cuts1 + cuts2;
+        if (cuts < mincuts) {
+            mincuts = cuts;
+            minix = i;
+        }
+    }
+    memo.insert(make_pair(key, mincuts));
+    return mincuts;
+}
+
+int minimum_palindrome_cuts_main(char** argv) {
+    string s{argv[1]};
+    unordered_map<pair<size_t, size_t>, int, PairHash> memo{};
+    fmt::print("{}\n", timeit_f([&]() { return minimum_palindrome_cuts<char>(s, 0, s.size(), memo); }));
+}
+
 int lcss_main(void) {
 
     vector<int> a{1, 6, 2, -1, 3, 55, 2, 4, 23, 5, 6, 7, 8, 9, 10};
@@ -420,7 +465,7 @@
     return 0;
 }
 
-int main(void) {
-    three_partition_main();
+int main(int argc, char** argv) {
+    minimum_palindrome_cuts_main(argv);
     return 0;
 }