问题

一条包含字母 A-Z 的消息通过以下方式进行了编码：

'A' -> 1
'B' -> 2
...
'Z' -> 26

给定一个只包含数字的非空字符串，请计算解码方法的总数。

示例

输入: "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

解答

class Solution {
public:
    int numDecodings(string s) {
        if (s.empty() || s[0]=='0') return 0;
        int pre = 1, cur = 1; // 初始化dp[-1], dp[0]

        //开始dp
        for (int i=1; i<s.size(); i++) {
            int tmp = cur;
            int use_1 = 1, use_2 = 0;
            if (s[i] == '0') {
                if (s[i-1]!='1' && s[i-1]!='2') return 0;
                use_1 = 0;
                use_2 = 1;
            }
            else if (s[i-1]=='1' || (s[i-1]=='2' && s[i]-'0'<'7')) use_2 = 1;
            cur = use_1 * cur + use_2 * pre;
            pre = tmp;
        }
        return cur;
    }
};

重点思路

这道题的评论里有人说“想dp函数5分钟，凑边界条件2小时”。这道题粗略的状态转移方程很好想，就是dp[i] = use_1 * dp[i-1] + use_2 * dp[i-2];，但是这两个常数什么时候取0和1需要讨论。

本题的动态规划之和前两个数有关，所以用pre表示dp[i-2]，cur表示dp[i-1]。

先考虑输入中不存在0的情况。这种情况下，解码存在歧义的充要条件为：上一个值等于2时，当前值小于等于6；或者当上一个值等于1时，当前可以取任意值。如果存在歧义，则将当前值单独解码，可能性为dp[i-1]种；将当前值与上一个值合起来解码，可能性为dp[i-2]种，加起来就是dp[i-1]+dp[i-2]。如果不存在歧义，那么只能单独解码，可能性为dp[i-1]。

再考虑存在0的情况。0只能和前一个值一起解码，只有10和20有意义，出现其他的说明解码错误，直接输出0。如果有意义的话，那么可能性为dp[i-2]，因为前一个数被0征用了，只有0前一个数的再前一个数所在的dp值有用。