题目描述：
有一种将字母编码成数字的方式：'a'->1, 'b->2', ... , 'z->26'。
现在给一串数字，返回有多少种可能的译码结果
数据范围：字符串长度满足 0<n≤90
进阶：空间复杂度 O(n)，时间复杂度O(n)
示例1：
输入：
"12"
返回值：
2
说明：
2种可能的译码结果（”ab” 或”l”）
示例2：
输入：
"31717126241541717"
返回值：
192
说明：
192种可能的译码结果
解题思路：
本题是动态规划的经典题目。有两个解题思路，动态规划和动态规划进阶(空间复杂度低)。
本题难点在于0的情况，10和20则只代表1种结果，11-19或21-26能代表2种结果，0不代表任何情况且可能会导致解码失败，1-9代表1种结果。
思路一：动态规划
- 用长度比字符串长度多1的dp存储结果数。dp[0]初始化为1；i从1开始，dp[i]存放的是前i个数字可能的结果，所以dp[1]也为1，dp[2]开始就要分情况了。
- 若i-1为0，则i-2必须为1或2，编码才可能成功，10和20有字母，30及之后都没有对应字母了。那么有dp[i]等于dp[i-2]，相当于dp[i]在dp[i-2]种可能的基础上多了一个双数字字母，多一个字母则结果数是一致的。
- 若i-2和i-1的位置能组合出11-19/21-26的数，则dp[i]相当于dp[i-1]和dp[i-2]之和。dp[i-1]表示截止到前i-1个数字可能的结果数，加上一个单数字对应的字母，是一类情况；dp[i-2]表示截止到前i-2个数字可能的结果数，加上一个双数字对应的字母，是一类情况。
- 若组合不出双数字字母，那就只能是单数字字母了，所以dp[i]等于dp[i-1]。相当于dp[i]在dp[i-1]种可能的基础上多了一个字母，多一个字母则结果数是一致的。
- 最后返回dp[size]，size是字符串长度，就是size个字符可能的结果数。
思路二：动态规划进阶
思路和思路一中基本一致。区别在于用pre和cur两个int数动态刷新，来实现动态规划，好处是空间复杂度降低，坏处是丢失了前面的结果数据只保留了最终结果。
建议看懂思路一代码再看思路二代码。
测试代码：
思路一：动态规划
class Solution { public: // 解码 int solve(string nums) { // 排除开头为0的情况 if(nums[0] == '0') return 0; // 动态规划 // dp[0]初始化为1；i从1开始，dp[i]存放的是前i个数字可能的结果，所以dp[1]也为1，dp[2]开始就要分情况了 vector<int> dp(nums.size()+1, 1); for(int i = 2; i <= nums.size(); ++i){ // 注意字符串下标是从0开始 // 若i-1为0，则当i-2为1或2时，编码才可能成功，10和20有字母，30及之后都没有对应字母了 if(nums[i - 1] == '0'){ // 若是10或20，则dp[i]等于dp[i-2]，相当于dp[i]在dp[i-2]种可能的基础上多了一个字母，多一个字母则结果数是一致的 if(nums[i - 2] == '1' || nums[i - 2] == '2') dp[i] = dp[i - 2]; else return 0; } // 若i-2和i-1的位置能组合出11-19/21-26的数，则dp[i]相当于dp[i-1]和dp[i-2]之和 // dp[i-1]表示前i-1个数字可能的结果数，加上一个单数字对应的字母，是一类情况 // dp[i-2]表示前i-2个数字可能的结果数，加上一个双数字对应的字母，是一类情况 else if(nums[i - 2] == '1' || (nums[i - 2] == '2' && nums[i - 1] > '0' && nums[i - 1] < '7')){ dp[i] = dp[i - 1] + dp[i - 2]; } // 若组合不出双数字字母，那就只能是单数字字母了，所以dp[i]等于dp[i-1] // 相当于dp[i]在dp[i-1]种可能的基础上多了一个字母，多一个字母则结果数是一致的 else{ dp[i] = dp[i - 1]; } } return dp[nums.size()]; } };
思路二：动态规划进阶
class Solution { public: // 解码 int solve(string nums) { // 排除开头为0的情况 if(nums[0] == '0') return 0; // 动态规划 // 用pre表示前i-1个字符的可能数，cur表示前i个字符的可能数 vector<int> dp(nums.size()+1, 1); int pre = 1; int cur = 1; for(int i = 2; i <= nums.size(); ++i){ // temp存储cur，因为cur马上要被覆盖了 int temp = cur; // 注意字符串下标是从0开始 // 若i-1为0，则当i-2为1或2时，编码才可能成功，10和20有字母，30及之后都没有对应字母了 if(nums[i - 1] == '0'){ // 若是10或20，则cur等于上一轮的pre，也就是比当前位置靠前2步的数值 if(nums[i - 2] == '1' || nums[i - 2] == '2') cur = pre; else return 0; } // 若i-2和i-1的位置能组合出11-19/21-26的数，则cur等于上一轮的cur和pre之和 // 上一轮的cur表示前i-1个数字可能的结果数，加上一个单数字对应的字母，是一类情况 // 上一轮的pre表示前i-2个数字可能的结果数，加上一个双数字对应的字母，是一类情况 else if(nums[i - 2] == '1' || (nums[i - 2] == '2' && nums[i - 1] > '0' && nums[i - 1] < '7')){ cur = cur + pre; } // 若组合不出双数字字母，那就只能是单数字字母了，所以cur相比上一轮的cur无数值变化，这段代码也可以删除，为了便于分情况理解我加上了 else{ cur = cur; } // 这一轮的pre等于上一轮的cur pre = temp; } return cur; } };
