力扣 解码方法 Python —— 动态规划

按照动态规划的思想，首先考虑前n位字符的解码方法数，在此基础上在往后推

用一维列表 dp 来记录状态，dp[0] 表示前1个字符的解码方法数，dp[3] 表示前4个字符的解码方法数，以此类推

分几种情况讨论：

如果字符串是空串，答案是0如果字符串第一位是0，答案是0字符串长度是1，答案是1

当字符串长度 > 1 且第一位不为 0，以 '11106' 为例：

因为第一位不为0，dp[0] = 1因为第一位和第二位的组合是 11，而且分开也是一种方法，所以 dp[1] = 2第三位开始可以利用前面的结果进行递推。设当前考虑的字符索引是 i， 表示一个字符/两个字符组合 是不是符合解码标准，得：。也就是当前考虑的字符，首先考虑单独成组的情况，有 ；其次，当前考虑的字符和它的前一个字符组合的情况，有 

给出代码如下：

class Solution(object):
    def numDecodings(self, s):
        dp = [0 for _ in s]

        def valid(chars):
            if chars[0] == '0':
                return False
            return int(1 <= int(chars) <= 26)
            # 判断子串是否在 [1, 26] 内，并定义首位为0时不合法

        if s:
            # 当不为空串
            if valid(s[0]):
                # 当第一位不为 0
                dp[0] = 1
                if len(s) > 1:
                    # 当字符串长度 > 1
                    dp[1] = valid(s[1]) + valid(s[:2])
                    # 两个字符分开 + 两个字符组合
                    for idx in range(2, len(s)):
                        dp[idx] = valid(s[idx]) * dp[idx - 1] + valid(s[idx - 1: idx + 1]) * dp[idx - 2]
                        # 递推传递
                    return dp[-1]
                else:
                    return 1
            else:
                return 0
        else:
            return 0