题目描述

一条包含字母 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;


    }
};