AcWing 59. 把数字翻译成字符串
class Solution:
def getTranslationCount(self, s):
"""
12258
1-> a
2-> b
12 -> m
状态表示: f[i] 前i位数字有多少种翻译方式
计算:两类相加
1. 第i位翻译成单独字母 f[i - 1]
2. i-1 和 i 联合翻译成一个字母 f[i - 2] 不一定有
0-25之间 不能0开头 >= 10 <= 25
10-25 : 1开头/ 2开头 21 22 23 24 25
边界:一个数都没有的话是1
"""
n = len(s)
f = [1] * (n + 1)
for i in range(2, n + 1):
f[i] = f[i - 1]
if s[i - 2] == '1' or (s[i - 2] == '2' and s[i - 1] <= '5'):
f[i] += f[i - 2]
return f[n]