一条包含字母A-Z的消息通过以下方式进行了编码： ‘A’ -> 1 ‘B’ -> 2 ‘C’ -> 3 … ‘Z’ -> 26 给定一个只包含数字的非空字符串。请计算解码方法的总数。 示例1： 输入：“12” 输出：2 解释：它可以解码为"AB"(1 2) 或者 “L”(12)。
示例2： 输入：“226” 输出：3 解释：它可以解码为"BZ" (2 26)，“VF” (22 6),或者 “BBF”(2 2 6)。
思想：dp[i]为译码方法总数；s[0]为’0’，直接返回0；dp[0]和dp[1]初始化为1；s[i]==‘0’时，如果s[i-1]==1或者2，0需要与前面的1或者2结合才能编码，则此时无新的编码方式，将dp[i+1]=dp[i-1]，如果前面的值不等于1或者2，则这个0无法参与编码，直接返回0。 当s[i]不为’0’时，若 s[i-1] 为’1’，或者s[i-1]为2且s[i]小于等于6大于等于1，则dp[i+1]=dp[i]+dp[-1]；否则dp[i+1]=dp[i];
代码：
int numDecodings(string s) { if (s[0] == '0') return 0; vector<int>dp(s.size() + 1); dp[0] = 1; dp[1] = 1; int i = 1; for (i; i < s.size(); ++i) { if (s[i] == '0') { if (s[i - 1] == '1' || s[i - 1] == '2') { dp[i+1] = dp[i - 1]; //由于s[1]指第二个下标，对应为dp[2], 所以dp的下标要比s大1，故为dp[i + 1] } else return 0; } else { if (s[i-1] == '1' || (s[i-1] == '2'&& s[i] <= '6')) { dp[i + 1] = dp[i - 1] + dp[i]; } else { dp[i + 1] = dp[i]; } } } return dp[s.size()]; }可以将dp数组用变量来代替，降低空间复杂度为O(1)
int numDecodings(string s) { if (s[0] == '0') return 0; int pre, curr;//保存前面状态和当前状态 pre = 1; curr = 1; int i; for (i = 1; i < s.size(); ++i) { int tmp = curr; if (s[i] == '0') { if (s[i - 1] == '1' || s[i - 1] == '2') { curr = pre;//当前状态等于上一个状态 } else { return 0;//30无法转换 } } else if (s[i - 1] == '1' || (s[i - 1] == '2'&&s[i] <= '6')) { curr = curr + pre; } pre = tmp; } return curr; }