2472定义DP[i]为以i结尾的回文字符串所能组成的最大数量的回文字符串数量有关键洞察为回文字符串长度最多为k与k1,对于k2及后面的所有情况都可以由贪心归纳为k与k1对于1到n的所有下标dp[i]可由i-k1与i-k两个下标得到即分别对应以i为结尾的字符串长度为k与k1的情况首先判断以i为结尾的子串在k与k1的情况下是否能构成回文字符串若都不能则dp[i]取0否则取max最终取1到n之间的dpMaxclass Solution { public: int maxPalindromes(string s, int k) { int ns.size(); vectorintdp(n,0); bool flagtrue; for(int i0;i(k1)/2;i){ if(s[i]!s[k-i-1]){ flagfalse; break; } } if(flag){dp[k-1]1;} flagtrue; for(int i0;i(k1)/2;i){ if(s[i]!s[k-i]){ flagfalse; break; } } if(flag){dp[k]1;} int resmax(dp[k-1],dp[k]); for(int i1;ik;i){dp[i]max(dp[i],dp[i-1]);} for(int ik1;in;i){ bool flag0true,flag1true; for(int j0;jk/2;j){ if(s[i-k1j]!s[i-j]){ flag0false; break; } } for(int j0;j(k1)/2;j){ if(s[i-kj]!s[i-j]){ flag1false; break; } } dp[i]max(dp[i],dp[i-1]); if(flag0){dp[i]max(dp[i-k]1,dp[i]);} if(flag1){dp[i]max(dp[i-k-1]1,dp[i]);} // for(int ji-k1;j(i1)/2;j){ // if(s[j]!) // } resmax(res,dp[i]); } return res; } };正解
