问题：
题目来源：力扣（LeetCode）
leetcode91.解码方法
难度：中等
分析： 注：提示里的s可以包含前导0的意思是给定的s中可能有前导0，但解码出来的字母不可以有前导0，例如“02”的解码方法总数为0。 解决方法： 1：DP
本题是一维DP，但情况比较多。 本题中的解法方法分为一位数可解码和两位数可解码，我们先假设所有的一位数和两位数都是合法的，那么到第i位时的解码方法数就可以写为dp[i] = dp[i - 1] + dp[i - 2]。因为我们可以将当前位单独解码和当前为与前一位共同解码。 基本的递推公式有了，我们开始讨论特殊情况，本题的特殊情况有两个，一个是递推公式为一位数解码时，0是非法字符；一个是两位数解码时，合法字符要在10到26之间。 首先我们讨论当前位是否是0，如果是0，当前位不能进行一位数解码，并且只有当前一位是1或者2的时候才能够进行合法的两位数解码。递推公式为： if s[i - 1] == ‘0’ and 0 < int(s[i - 2]) <= 2：dp[i] = dp[i - 2]， if s[i - 1] == ‘0’ and int(s[i - 2]) <= 0 or int(s[i - 2]) >= 3：dp[i] = 0 （这里的s取i - 1是因为添加了辅助值，后面讨论） 如果当前位不是0，那么当前位的一位数解码肯定是合法的，现在我们要讨论两位数解码是否也合法，于是我们查看当前位是否和前一位组成合法的两位数，递推公式为： if s[i - 1] ！= ‘0’ and 10 < int(s[i - 2] + s[i - 1] <= 26：dp[i] = dp[i - 2] + dp[i - 1]， if s[i - 1] ！= ‘0’ and int(s[i - 2]) < 10 or int(s[i - 2]) > 26：dp[i] = dp[i - 1]
现在我们获得了递推公式，还有一个问题是base case的初始化。最一般的情况，我们将dp[i]设为到是s[i]字母为止的解码方法总数。这时候我们需要初始化dp[0]和dp[1]。初始化方法与递推公式相同。
if n>=2: #为了方便理解初始化dp[1],也可初始化dp长度n+1来避免此步骤 dp[1] = 1 if s[1]=="0" and 0<int(s[0])<=2 \ else 0 if s[1]=="0" \ else 2 if 10<int(s[0]+s[1])<=26 \ else dp[0]但我们可以借助辅助值来简化base case。将dp数组增加一位。设dp[i]为长度为s的长度为i时的解码总数。这时候的初始化只需要下面这几句：
dp = [0]*(n + 1) #dp[i]表示s从下标长度为i的字符串的方法总数 dp[0] = 1 dp[1] = 1 if s[0]!="0" else 0dp[0]代表字符串长度为空时的解码方法为1，这个base case初始值设置考虑可以从dp[2]推导过来。dp[1]的值是直接设定的，当s[0]可以进行一位数解码的时候，dp[1]的解码方法为一种，否则为0。那么dp[0]为什么要直接设置为1呢？ 是因为我们后序递推使用到这个值的地方只有在求dp[2]的时候，计算dp[i-2]时需要用到dp[0]，dp[i-1]的含义时当前值和前一位可以进行两位数解码，比如“12”，那么此时的dp[0]应该为1，以保证这个合法的两位数解码可以被计算到解码方法的总数中去。所以dp[0]可以初始化为1。 使用辅助值进行初始化可以带来很多快速的初始化方法，但边界值的寻找需要一定技巧，要慢慢积累。 本题题解：
class Solution: def numDecodings(self, s: str) -> int: n = len(s) dp = [0]*(n + 1) #dp[i]表示s从下标长度为i的字符串的方法总数 dp[0] = 1 dp[1] = 1 if s[0]!="0" else 0 for i in range(2, n + 1): if s[i - 1] == '0': if 0 < int(s[i - 2]) <= 2: dp[i] = dp[i - 2] else: dp[i] = 0 else: if 10 < int(s[i - 2] + s[i - 1]) <= 26: dp[i] = dp[i - 2] + dp[i - 1] else: dp[i] = dp[i - 1] return dp[-1]