3.一条包含 A-Z 字母的信息，用如下的数字加密方法进行加密 'A' -> 1 'B' -> 2 ... 'Z' -> 26 给定一个已经用上述加密方法进行加密的非空字符串， 请返回可能的解密结果的数量。Example 1: Input: "12" Output: 2 Explanation: It could be decoded as "AB" (1 2) or "L" (12). Example 2: Input: "226" Output: 3 Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6). class Solution { public: int numDecodings(string s) { } };

这道题是动态规划问题。我们用 dp[i] 表示字符串 s 的前 i 个字符的解码方法总数。对于字符串 s 的第 i 个字符，如果它能单独解码成一个字母，则 dp[i] += dp[i-1]。如果它能与前一个字符组成一个字母，则 dp[i] += dp[i-2]。最终返回 dp[n]，其中 n 是字符串 s 的长度。

需要注意的是，如果字符串 s 的第一个字符为 '0'，则无法解码，直接返回 0。

代码如下：

class Solution {
public:
    int numDecodings(string s) {
        int n = s.length();
        if (n == 0 || s[0] == '0') return 0;
        vector<int> dp(n+1, 0);
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            int num1 = stoi(s.substr(i-1, 1));
            int num2 = stoi(s.substr(i-2, 2));
            if (num1 >= 1 && num1 <= 9) dp[i] += dp[i-1];
            if (num2 >= 10 && num2 <= 26) dp[i] += dp[i-2];
        }
        return dp[n];
    }
};