‘A‘ -> 1‘B‘ -> 2...‘Z‘ -> 26

 

 

方案：
算法：动态规划；

函数设计：
     我们使用数组f[i]， 存储长度为 i 的 s 串可以被翻译的方法数。
     char类型的cur表示长度为i的s‘的最后一个字符，pre表示长度为i的s‘的倒数第二个字符。
     （1）当s为空时，返回0；
     （2）当s不为空，但s[0] = ‘0‘时 ， 返回 0。 因为此时，s不可能被翻译为A-Z组成的字符串。
     （3）当s不为空，且开始字母不为‘0’时，初始化f[0] = 1, f[1] = 0;
                  a，当pre = ‘1‘, 且 cur != ‘0‘时， f[n] = f[n-1] + f[n-2]; 因为此时字符串i必然为...1x = ...1 + x， 或者 ...1x = ... + 1x;
                      由 ...1 + x的方式组成 ...1x时，译码方法数等于f[n-1];
                      由 ... + 1x的方式组成 ...1x时，译码方法数等于f[n-2];
                  b，当pre = ‘2‘, 且 cur 的取值为{‘1‘, ‘2‘, ‘3‘, ‘4‘, ‘5‘, ‘6‘}的其中之一时，f[n] = f[n-1] + f[n-2];原理同上。
                  c，当cur = ‘0‘ 时，
                      c1, 如果pre = ‘1‘ 或者 pre = ‘2‘时，译码方法数必然等于 f[n-2],因为此时译码方式必然为...+ 10 或者 ... + 20。 不可能为...1 + 0这样的方式。
                      c2, 如果pre 不为‘1‘,‘2‘, 译码方法数必然为0
                  d，其余情况译码方法 f[n] = f[n-1];