这题用到的是动态规划算法。主要的思想和分治法有点像，将大大的问题分解成底层的小问题，动态规划就是把问题从最小的单元开始，逐渐增加问题规模，每次后面的结果都与前面相关。我咬字不清，下面就结合这个题目来讲解吧。

　　问题输入的是一串数字1~26（A~Z），求解可以形成多少种字符串。我们首先不要拿一大窜字符来考虑，我们想的思路是：先取1个数字，一种排法；第2个数字，可能与第1个数字结合，或者单独成字母；第3个数字，可能与第2个数字结合，或者单独成字母。。。。思路就是这样了。

　　每个新增加的字母有三种可能出现的情况（用pre代表前一个数字，post代表新增数字）：

为了讲解方便，我们为每个数字设计了一个数组s，每个数字都代表相应的数组的值，代表新增这个数字时，整个字符串形成的种类。post为s2。

　　①“pre+post”形成的数字大于26，则post只能单独成字母，此时的字符串种数和前一个相同。则s2=s1。

　　②“pre+post”形成的数字在1~26之间，此时有两种选择，单独成字母或者与前一个结合。单独成字母时，其字符串种数和前一个相同；与前一个结合时，其种数与前前个的种树相同。总的种数为前两个字母的种类数之和。则s2=s1+s0.

　　③“post=0”，此时只能形成“10”，一次它的种类数只能为前前个字母的种类数。则s2=s0。

具体代码如下：

1 // Problem#: 1001 2 // Submission#: 1448210 3 // The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License 4 // URI: http://creativecommons.org/licenses/by-nc-sa/3.0/ 5 // All Copyright reserved by Informatic Lab of Sun Yat-sen University 6 #include 
     
       7 #include 
      
        8 using namespace std; 9 10 int main()11 {12     string str;13     while(cin>>str&&str!="0")14     {15         int s1=1,s2=1,s3=1;16         for(int i=1;i