# ---
# title: 132. Palindrome Partitioning II
# id: problem132
# author: Tian Jun
# date: 2020-10-31
# difficulty: Hard
# categories: Dynamic Programming
# link: <https://leetcode.com/problems/palindrome-partitioning-ii/description/>
# hidden: true
# ---
# 
# 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`.
# 
# 
# 
# **Example 1:**
# 
#     
#     
#     Input: s = "aab"
#     Output: 1
#     Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.
#     
# 
# **Example 2:**
# 
#     
#     
#     Input: s = "a"
#     Output: 0
#     
# 
# **Example 3:**
# 
#     
#     
#     Input: s = "ab"
#     Output: 1
#     
# 
# 
# 
# **Constraints:**
# 
#   * `1 <= s.length <= 2000`
#   * `s` consists of lower-case English letters only.
# 
# 
## @lc code=start
using LeetCode

## add your code here:
## @lc code=end
