从当前位置往前看1个位置或2个位置。
class Solution:
def numDecodings(self, s: str) -> int:
if not s: return 0
valid = {str(i) for i in range(1, 27)}
dp = {-1: 1}
dp[0] = int(s[0] in valid) # [0]特殊处理
for i in range(1, len(s)): # 注意从1开始
dp[i] = 0
if s[i] in valid:
dp[i] += dp[i - 1]
if s[i - 1: i + 1] in valid:
dp[i] += dp[i - 2]
return dp[len(s) - 1]