leetCode 91. 解码方法

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

'A' -> 1
'B' -> 2
...
'Z' -> 26
给定一个只包含数字的非空字符串，请计算解码方法的总数。

示例 1:

输入: "12"
输出: 2
解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。

示例 2:

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

????    https://leetcode-cn.com/problems/decode-ways

动态规划: 解码到第i个字母的方案个数: 如果第i个字母非0的话就可以把第i个字母单独解码一次,这样f[i]就转换成了f[i - 1] 因为第i个元素解码方式已经确定了
如果(s[i] - '0') * 10 + s[i] - '0' 大于等于10,且小于等于26的话就可以把后面的两个字母进行解码,此时求f[i] 就转换成了求 f[i - 2]  因为第i - 1个元素和第i个元素解码方式已经确定了  
这样来说的话其实这道题的思路和求路径和的那道题思路是一样的:解码到第i个元素可以有2条方式到达这种状态一种是从f[i - 1]来，一种是从 f[i - 2]来
    f[i] = f[i - 1] + f[i - 2] 但是注意一点:f[i - 1] 和 f[i - 2] 不一定是实时都存在的。

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        int f[n + 1] = {1};
        for (int i = 1; i <= n; ++i){
            if (s[i - 1] != '0') f[i] += f[i - 1]; // 最后一个元素是'0'的话是没法解码成一个字符的因为题目中0没有对应的原码
            if (i - 2 >= 0){
                int  t = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
                if (t >= 10 && t <= 26) f[i] += f[i - 2];  // 注意这里 t是大于等于10且小于等于26的时候才可以将两个元素一起进行解码,如果0 <= t && t <= 9 的话那么就有s[i-1] = '0' s[i] != '0',这种 0_ 型不能被看成一个两位数进行解码,只能一个一个元素的解码。
            }
        }
        return f[n];
    }
};