首页 > 代码库 > [LeetCode] Palindrome Partitioning II （DP）
[LeetCode] Palindrome Partitioning II （DP）
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.
For example, given s = "aab", Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.
避免用递归产生低效的程序，用DP的方法：
class Solution { public: int minCut(string s) { if(s.empty()) return 0; int n = s.size(); vector<vector<bool>> pal(n,vector<bool>(n,false));//记录Si到Sj之间是否形成回文 vector<int> d(n);//记录Si到S末尾分割能形成回文的最小分割数 for(int i=n-1;i>=0;i--) { d[i]=n-i-1; for(int j=i;j<n;j++) { if(s[i]==s[j] && (j-i<2 || pal[i+1][j-1])) { pal[i][j]=true; if(j==n-1) d[i]=0; else if(d[j+1]+1<d[i]) d[i]=d[j+1]+1; } } } return d[0]; } };
每个两两之间都考虑到，需要O（n^2）次数，然后只考虑其中能构成回文的子序列，即Si和Sj之间能构成回文的子序列pal[i][j]=true，仔细体会一下。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。