链接132. 分割回文串 II题解. - 力扣LeetCode. - 力扣LeetCodeLintCode 炼码 - 更高效的学习体验dp[i] 表示前i个字段需要最少划分几次每段都可以是回文dp[i] 表示前i个字段需要最少为阶段每段都可以是回文这种需要dp[n]-1因为结果求的是划分次数需要枚举最后一个分割点在哪里,j [0,i)class Solution { public: bool is_same(const std::string s, int begin, int end) { while(begin end) { if(s[begin] ! s[end]) { return false; } begin; --end; } return true; } int minCut(string s) { // 两种方法 // 第一种same[i][j]表示s[i][j]是否为回文串same[i][j]可以预处理 // 第二种通过is_same判断 vectorvectorbool same(s.size(), vectorbool(s.size(), true)); for(int len 2; len s.size(); len) { for(int j 0; jlen s.size(); j) { if(len 2) { if(s[j] s[jlen-1]) { same[j][jlen-1] true; } else { same[j][jlen-1] false; } } else { if(same[j1][jlen-2] s[j] s[jlen-1]) { same[j][jlen-1] true; } else { same[j][jlen-1] false; } } } } vectorint dp(s.size(), s.size()); // dp[i]表示以i下标为末尾字符的字符串最少分割次数 // dp[i] min(dp[i], dp[j]1) //0 j i // 如果s[j1,i]为回文串则dp[i]可以由dp[j]1得来 for(int i 0; i s.size(); i) { //if(is_same(s, 0, i)) { if(same[0][i]) { dp[i] 0; continue; } for(int j 0; j i; j) { //if(is_same(s, j1, i)) { if(same[j1][i]) { dp[i] min(dp[i], dp[j]1); } } } return dp[s.size()-1]; } };class Solution { public: /** * param s: A string * return: An integer */ int minCut(string s) { // write your code here int len s.size(); if (len 0) { return 0; } vectorvectorbool memo(len, vectorbool(len, false)); for (int i 0; i len; i) { memo[i][i] true; if (i 1 len s[i] s[i1]) { memo[i][i1] true; } } //cout haha endl; for (int i 3; i len; i) { for (int begin 0; begin i - 1 len; begin) { int end begin i -1; if (s[begin] s[end] memo[begin1][end-1]) { memo[begin][end] true; } } } // cout haha endl; vectorint dp(len1, INT_MAX); dp[0] 0; for (int i 1; i len; i) { for (int j 0; j i; j) { if (j 0 memo[j][i-1] dp[j] ! INT_MAX) { dp[i] 0; } else if (memo[j][i-1] dp[j] ! INT_MAX) { dp[i] min(dp[i], dp[j] 1); } } } return dp[len]; } }; 
长河君 · 2026/10/24 1:39:32 · 阅读 1.2k 划分型-132. 分割回文串 II（划分dp）
链接132. 分割回文串 II题解. - 力扣LeetCode. - 力扣LeetCodeLintCode 炼码 - 更高效的学习体验dp[i] 表示前i个字段需要最少划分几次每段都可以是回文dp[i] 表示前i个字段需要最少为阶段每段都可以是回文这种需要dp[n]-1因为结果求的是划分次数需要枚举最后一个分割点在哪里,j [0,i)class Solution { public: bool is_same(const std::string s, int begin, int end) { while(begin end) { if(s[begin] ! s[end]) { return false; } begin; --end; } return true; } int minCut(string s) { // 两种方法 // 第一种same[i][j]表示s[i][j]是否为回文串same[i][j]可以预处理 // 第二种通过is_same判断 vectorvectorbool same(s.size(), vectorbool(s.size(), true)); for(int len 2; len s.size(); len) { for(int j 0; jlen s.size(); j) { if(len 2) { if(s[j] s[jlen-1]) { same[j][jlen-1] true; } else { same[j][jlen-1] false; } } else { if(same[j1][jlen-2] s[j] s[jlen-1]) { same[j][jlen-1] true; } else { same[j][jlen-1] false; } } } } vectorint dp(s.size(), s.size()); // dp[i]表示以i下标为末尾字符的字符串最少分割次数 // dp[i] min(dp[i], dp[j]1) //0 j i // 如果s[j1,i]为回文串则dp[i]可以由dp[j]1得来 for(int i 0; i s.size(); i) { //if(is_same(s, 0, i)) { if(same[0][i]) { dp[i] 0; continue; } for(int j 0; j i; j) { //if(is_same(s, j1, i)) { if(same[j1][i]) { dp[i] min(dp[i], dp[j]1); } } } return dp[s.size()-1]; } };class Solution { public: /** * param s: A string * return: An integer */ int minCut(string s) { // write your code here int len s.size(); if (len 0) { return 0; } vectorvectorbool memo(len, vectorbool(len, false)); for (int i 0; i len; i) { memo[i][i] true; if (i 1 len s[i] s[i1]) { memo[i][i1] true; } } //cout haha endl; for (int i 3; i len; i) { for (int begin 0; begin i - 1 len; begin) { int end begin i -1; if (s[begin] s[end] memo[begin1][end-1]) { memo[begin][end] true; } } } // cout haha endl; vectorint dp(len1, INT_MAX); dp[0] 0; for (int i 1; i len; i) { for (int j 0; j i; j) { if (j 0 memo[j][i-1] dp[j] ! INT_MAX) { dp[i] 0; } else if (memo[j][i-1] dp[j] ! INT_MAX) { dp[i] min(dp[i], dp[j] 1); } } } return dp[len]; } };