leetcode/solutions/132.Palindrome_Partitioning_II at master · illuz/leetcode · GitHub

Name		Name	Last commit message	Last commit date
parent directory ..
AC_dp_n^2.cpp		AC_dp_n^2.cpp
AC_dp_n^2.java		AC_dp_n^2.java
AC_recursive_2^n.cpp		AC_recursive_2^n.cpp
TLE_recursive_2^n.cpp		TLE_recursive_2^n.cpp
readme.md		readme.md

readme.md

132. Palindrome Partitioning II (Hard)

链接：

题目：https://leetcode.com/problems/palindrome-partitioning-ii/
代码(github)：https://github.com/illuz/leetcode

题意：

把一个字符串分割，使每一部分都是回文。问最少的割数。

分析：

(C++) 跟上题一样，递归求过去，不过会 TLE
优化一，考虑对 1 进行优化，可以预处理子串是否是回文，就不用在这步重复算了
优化二，既然可以用 DFS，当然可以记忆化了
(Java) 既然可以用记忆化，当然可以写成 DP 了
(C++) 在 DP 的时候，可以不用预处理判断是否回文，直接分奇偶讨论，见：not need a table for palindrome