可以发现就是约束版的f(n) = f(n-1) + f(n-2);,其中如果是s[n-1]为0,f(n-1) = 0,于是f(n) = f(n-2),因为0无法单独解码。而f(n-2)的条件则是必须在1与26之间,否则f(n) = f(n-1)。
class Solution:
def numDecodings(self, s: str) -> int:
n = len(s)
if n == 0 or s[0] == '0':
return 0
dp = [0] * (n+1)
dp[0] = 1 #辅助,没有实际意义
for i in range(n):
if s[i] == '0':
dp[i+1] = 0
else:
dp[i+1] = dp[i] #f(n) = f(n-2)
if i > 0 and (s[i-1] == '1' or (s[i-1] == '2' and s[i] <= '6')):
dp[i+1] += dp[i-1] #f(n) = f(n-2)+f(n-1)
return dp[n]