Given a string s, partition it so every substring is a palindrome. Return the minimum number of cuts needed. For "aab", one cut gives ["aa", "b"], both palindromes. For "a", zero cuts needed.
This combines two smaller tasks: checking if substrings are palindromes, and finding minimum cuts. Read the constraints carefully, especially the input size. This tells you what time complexity you need. Try to find the recursive structure: how does solving smaller instances help solve the full problem?