题目：有一种将字母编码成数字的方式：'a'->1, 'b->2', ... , 'z->26'。

现在给一串数字，给出有多少种可能的译码结果。

 

想法：

该题就是动态规划问题，建议在写这题之前明白“背包问题”会好理解很多。

 

---

 

参考代码：

 1 #include<iostream>
 2 using namespace std;
 3   
 4 int numDecodings(string s)
 5 {
 6         if(!s.size() || s.front() == '0') return 0;
 7         int r1 = 1, r2 = 1;
 8         for (int i = 1; i < s.size(); i++)
 9         {
10             if (s[i] == '0') // 当当前i位为‘0’时，只有与前一位结合在一起算一个字母，即：10,20； 所以，此时r1（最大可能）不增加。
11                 r1 = 0; // 这里赋值0，是为了下一个if中r1 = r2 + r1; 将r1赋值为r2.
12             if ((s[i-1] == '1') || (s[i-1] == '2' && s[i] <= '6'))
13             {
14                 r1 = r2+r1; // r1记录的是：第i位算一个字母的情况 + 第i-1位与i位合为一个字母的情况 （也就是最大的可能）
15                 r2 = r1-r2; // r2记录的是：第i-1位之前的所有可能（不包含i-1位）
16             }
17             else
18                 r2 = r1;
19         }
20         return r1;
21 }
22 int main()
23 {
24     string s;
25     while(cin >> s)
26     {
27         cout << numDecodings(s) << endl;
28     }
29     return 0;
30 }