Leetcode-解码方法（中等）

题目描述

一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
'A' -> 1
'B' -> 2
...
'Z' -> 26
要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"111" 可以将 "1" 中的每个 "1" 映射为 "A" ，从而得到 "AAA" ，或者可以将 "11" 和 "1"（分别为 "K" 和 "A" ）映射为 "KA" 。注意，"06" 不能映射为 "F" ，因为 "6" 和 "06" 不同。
给你一个只含数字的 非空 字符串 num ，请计算并返回 解码 方法的 总数 。
题目数据保证答案肯定是一个 32 位 的整数。

动态规划：
若当前位为0，则判断前一位是否是1/2，如果是：f[i]=f[i-2] 这样0只能和前一位绑定在一起；如果不是，return 0；
若当前位为和前一位满足两位数且在26范围内，f[i] = f[i - 2] + [i - 1]
否则，f[i] =[i - 1]

考虑到dp数组想和s索引对应，所以相当于从s[-1]=1,s[0]=1,用a和b代替，否则越界了

class Solution {
public:
    int numDecodings(string s) {
        if (s[0] == '0') return 0;
        int a = 1, b = 1, ans = 1;//a代表f[i-2]，b代表f[-1]，ans至少有一个，省略了length=1的情况
        for (int i = 1; i < s.size(); i++) {//i表示字符串索引
            if (s[i] == '0') {
                if (s[i - 1] != '1' && s[i - 1] != '2') return 0;
                else ans = a;//f[i]=f[i-2] 易错点
            }
            else if (s[i - 1] == '1' || s[i - 1] == '2' && s[i] <= '6')
                ans = a + b;//f[i]=f[i-2]+[i-1]
            else
                ans = b;//f[i]=f[i-1]
            a = b;
            b = ans;
        }
        return b;


    }
};