c++一条包含字母 A-Z 的消息通过以下映射进行了编码: 'A'->"1" 8'->"2" ... Z'->"26" 要解码已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母(可能有多种方法)。例如，"11106”可以映射为: "AAJF"，将消息分组为 (1110 6)"KJF"，将消息分组为 (11 10 6)但是，消息不能分组为 (1 11 06)，因为“06”不能映射为”，这是由于"6”和“06”在映射中并不等价。 给 Jim 一个只含数字的非空字符串 s，请计算并返回解码方法的总数。题目数据保证答案肯定是一个 32 位的整数。代码实现

以下是C++的代码实现：

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        vector<int> dp(n+1, 0);
        dp[n] = 1;
        for (int i = n-1; i >= 0; i--) {
            if (s[i] == '0') {
                dp[i] = 0;
            } else {
                dp[i] += dp[i+1];
                if (i < n-1 && (s[i] == '1' || (s[i] == '2' && s[i+1] <= '6'))) {
                    dp[i] += dp[i+2];
                }
            }
        }
        return dp[0];
    }
};

时间复杂度为 O(n)，空间复杂度为 O(n)。