我们查看这样一个例子，考虑如何独立地打印出区间[i:j]（即不受区间左边界外的字符影响）。我们记最少的打印操作是dp[i][j].
a X X X X a X X a X X X a X X X
i x y z j
首先，第一个字符'a'是无法靠打印其他字符所顺带得到，所以必须主动打印。那么我们显然会思考这样一个问题，我们可以顺带多打印一些'a'，岂不是能够方便后续对'a'的打印？想到这里，是不是觉得无脑把整个[i:j]区间都打印成'a'最省事？理论上是，但对于我们拆分问题没有帮助。假设最优解里，位置z上的'a'并不是和位置i上的'a'一起打印出来，那么上述的将[i:j]都打印成'a'的操作就没有意义，因为它并不能帮助省下位置z的打印操作。除非我们限定：位置z上的'a'是和位置i一起打印出来的，那么我们就知道第一步操作必须将区间[i:z]都打印成'a'。那么之后问题如何转化呢？因为位置z不能再被打印，所以整个区间被割裂成了两部分，即[i:z-1]和[z+1:j]. 首先观察后面的[z+1:j]，显然它不受自己区间左边界外的字符影响（因为打印了位置z后，不允许其他字符的打印范围可以跨越z），所以最少打印操作就是dp[z+1][j]. 再观察前面的[i:z-1]，它显然也不受自己区间左边界外的字符影响，所以最少打印操作是dp[i][z-1].
特别注意，这种情况下，我们记dp[i][j] = dp[i][z-1] + dp[z+1][j]. 那么位置z上的打印操作哪里去了？这是因为我们打印[i:z-1]时必然会打印第一个'a'，顺手将其打印到位置z即可。
由此我们总结，将dp[i][j]分解的关键，就在于考察首字符“有意义的”打印范围可以持续到哪里，所谓的有意义，其实就是说打印范围的最后一个'a'字符要限定和首字符一起打印出来后就不会再被覆盖。如果未来还会被覆盖，那么首字符的打印范围就没有必要延伸到哪里。在上面的例子里，这样的打印范围其实只有四种选择，就是从i到i，从i到x，从i到y，从i到z，分别对应了“最后一个与首字符一起打印的位置”是i, x，y和z。这四种情况是互斥且互补的。所以我们可以将dp[i][j]的求解，就转化为在这四类后续中取最优解：
dp[i][j] = min { dp[i][k-1] + dp[k+1][j] } for all i<=k<=j && s[k]==s[i]特别地，当k==i时，上述的表达式有些不方便，可以单独分开来写一下：
dp[i][j] = 1 + dp[i+1][j];
dp[i][j] = min { dp[i][k-1] + dp[k+1][j] } // for i<k<j && s[k]==s[i]如果有人思考地比较深入，或许会有这样的疑问。在第一步拆分dp[i][j] = dp[i][z-1] + dp[z+1][j]的情况下，我们已经认定首字母的打印范围从i延伸到了z。但是我们在接下来计算dp[i][z-1]的时候，类似地，会讨论首字母的打印范围从i延伸到y的情况。这两个前提是否矛盾？其实不矛盾。我们在讨论dp[i][j]时，其实讨论的是在区间[i:j]内最后一个与首字符一起打印的位置。我们在讨论dp[i][z-1]时，其实讨论的是在区间[i:z-1]内最后一个与首字符一起打印的位置。对于不同的区间，最后一个与首字符一起打印的位置是可以不同的。事实上，真正的首字符打印范围，可以一直延伸到全局最后一个与首字符一起打印的那个位置。
最后，因为是典型的区间型DP，我们需要从小区间推导出大区间，所以两层循环的模板如下：
for (int len=2; len<=N; len++)
for (int i=0; i<=N-len; i++)
{
int j = i+len-1;
dp[i][j] = 1+dp[i+1][j];
for (int k=i+1; k<=j; k++)
{
if (s[k]==s[i])
dp[i][j] = min(dp[i][j], dp[i][k-1] + ((k+1>j)?0:dp[k+1][j]));
}
} 初始条件是：
- dp[i][j]==1 when i==j，即len的长度为1;
- dp[i][j]==0 when i>j. 注意这个是允许遇到的，比如上面的例子，如果区间[i:j]里面的s[j]==s[i]，于是k可以取到j，转移方程的dp[k+1][j]就会出现这种情况。