动态规划
思路:
用dp[i]表示s从0到下标i的子串的解码总数。下面分情况讨论：
如果字符串为空或者首字符为‘0’，则直接返回0
如果首字符s[0]不为0，则dp[0] = 1
dp[0]=1的情况下:
在确定了dp[0]和dp[1]后，继续进行后续处理：
代码:
class Solution: def numDecodings(self, s: str) -> int: if not s or s[0]==‘0‘: return 0 dp = [1] for i in range(1,len(s)): if s[i] == ‘0‘: if s[i-1] == ‘1‘ or s[i-1] == ‘2‘: if i == 1: dp.append(1) else: dp.append(dp[i-2]) else: return 0 elif s[i-1] == ‘1‘ or (s[i-1]==‘2‘ and s[i]>=‘1‘ and s[i]<=‘6‘): if i == 1: dp.append(2) else: dp.append(dp[i-1]+dp[i-2]) else: dp.append(dp[-1]) return dp[-1]
原文：https://www.cnblogs.com/nilhxzcode/p/13156947.html