Given a string s, partition s such that every substring of the partition is a palindrome. Return the minimum cuts needed for a palindrome partitioning of s.
Though I was able to code O(N^3) solution but facing problem in O(N^2) optimization
This is the optimized solution explanation
In the very first line "cut[i] is the minimum of cut[j – 1] + 1 (j <= i), if [j, i] is palindrome"
Why is this the case? Formal proof is not essential, intuition will also do.