【问题】
一条包含字母 A-Z 的消息通过以下方式进行了编码：
'A' -> 1
'B' -> 2
…
'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]表示前i-1个数字所解码的字符串数量，因此对于i来说，且dp长度为s.length()+1，其有两种编码方式：
-
由一个数字编码而来，即最后一个数字s[i-1]不为零即可，从而需要加上前i-2的解码数量，即dp[i] += dp[i-1]
-
由两个数字编码而来， 即最后一个数字s[i-2]和s[i-1]构成的两位数字在1~26之间，从而要加上前i-3个数字的解码数量，即dp[i] +=dp[i-2]
我们只需要判断这两个条件，如果成立了，就加上相应的结果即可！
class Solution { public: int numDecodings(string s) { if (s[0] == '0') return 0; vector<int> dp(s.length() + 1); dp[0] = dp[1] = 1; for(int i = 2; i <= s.length(); i++){ if(s[i-1] != '0'){ dp[i] += dp[i-1]; } if((s[i-2] == '1') || (s[i-2] == '2' && s[i-1] <= '6')){ dp[i] += dp[i-2]; } } return dp[s.length()]; } };