动态规划|给定一个字符串，切分该字符串，使得到的子串都是回文字符串，计算最少的切分次数。
给定一个字符串，计算出将该字符串切分成若干个回文子串所需的最少切分次数。
直接计算一个字符串的切分次数，很难，可以试着缩小问题规模，从而发现规律。
假设给出的字符串可以用ps[0->iend]表示，ps[0],ps[1],...,ps[iend]都是字符。
min_count(i,j)，表示将字符串ps[i->j]切分成若干回文字符串所需的最少切分次数。
min_count(i,i)=0;
min_count(i,i+1)=(ps[i]!=ps[i+1]?1:0);
当j>=i+2时，如果ps[i->j]是回文字符串，则min_count(i,j)=0；
如果ps[i->j]不是回文字符串，能否通过子问题的解计算min_count(i,j)；这就引发了两个新问题：（1）、原问题的解与子问题的解之间的关系。（2）、怎样判断ps[i->j]是不是一个回文字符串。
对于问题（1），若ps[i->j]最后在t处切分得到了若干回文字符串，使得切分ps[i->j]所需的次数最少，则切分ps[i->t]和ps[(t+1)->j]的次数也应该是最少的，用反证法容易证明。这样就可以考虑用动态规划法求解。其中t=i,(i+1),...,(j-1)。
总之，min_count(i,j)=Min{min_count(i,t),min_count(t+1,j)}+1。
其中，j>=i+2;
t=i,(i+1),...,(j-1)。
对于问题（2），若ps[i->j]是回文字符串，则ps[(i+1)->(j-1)]必是回文字符串，而且ps[i]==ps[j]。反之已成立。
用is_palindrome(i,j)表示ps[i->j]是否是回文字符串。
is_palindrome(i,j)=true，若ps[i->j]是回文字符串;
is_palindrome(i,j)=false，若ps[i->j]不是回文字符串。
is_palindrome(i,i)=true;
is_palindrome(i,i+1)=(ps[i]==ps[i+1]?true:false);
当j>=i+2时，
is_palindrome(i,j)=(is_palindrome(i+1,j-1)?(ps[i]==ps[j]?true:false):false);
综上可知：
（1）、min_count(i,i)=0。
（2）、min_count(i,i+1)=(ps[i]!=ps[i+1]?1:0)。
（3）、若j>=i+2，如果is_palindrome(i,j)=true，则min_count(i,j)=0;
如果is_palindrome(i,j)=false，则min_count(i,j)=Min{min_count(i,t),min_count(t+1,j)}+1;
其中t=i,(i+1),...,(j-1)。
【动态规划|给定一个字符串，切分该字符串，使得到的子串都是回文字符串，计算最少的切分次数。】源码在github上（https://github.com/wjt2015/palindrome_cut）。
推荐阅读
- 一个人的旅行，三亚
- 一个小故事，我的思考。
- 一个人的碎碎念
- 七年之痒之后
- 我从来不做坏事
- 异地恋中，逐渐适应一个人到底意味着什么（）
- 迷失的世界（二十七）
- live|live to inspire 一个普通上班族的流水账0723
- 遗憾是生活的常态，但孝顺这件事，我希望每一个人都不留遗憾
- NO.38|NO.38 我不是嫁不出去，而是不想嫁