来源：力扣（LeetCode）
链接：https://leetcode.com/problems/decode-ways
这道题很明显要用动态规划，但是状态转移方程看上去比较复杂，因为有0的存在。比如，如果存在连续包含两个0的情况，则必然输出0；再比如，如果出现类似于80的情况，也必然输出0。
以下状态转移方程，可以完美解决这个问题。
-
1 <= s[i] <= 9。则ans[i+1] += ans[i]； -
10 <= s[i-1]s[i] <= 26。则ans[i+1] += ans[i-1]； - 如果以上两个都不成立，则
s[i]必然是0，且无法和s[i-1]组成10或者20，则意味着该字符串无法表示有效字符，直接输出0，结束运行。
再看初始值，为什么要把ans[0]设为1呢？因为如果s[0]s[1] = 10，则ans[2] = ans[0]，而ans[2]应该是1。
完整代码：
class Solution:
def numDecodings(self, s: str) -> int:
if not s or s[0] == '0':
return 0
elif len(s) == 1:
return 1
ans = [None for _ in range(len(s)+1)]
ans[0] = 1 #这个初值很重要
ans[1] = 1
for i in range(1, len(s)):
ans[i+1] = 0
succ = 0
if int(s[i])>=1 and int(s[i])<=9:
ans[i+1] += ans[i]
succ = 1
if int(s[i-1] + s[i])>=10 and int(s[i-1] + s[i])<=26:
ans[i+1] += ans[i-1]
succ = 1
if succ == 0:
return 0
return ans[len(s)]
运行结果：
