剑指Offer46-把数字翻译成字符串
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
示例 1:
输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
提示：
- 0 <= num < 2^31
来源：力扣（LeetCode）
链接：力扣
一解
使用动态规划，分为二类，设 dp[j] 为前 j 个数字，翻译的数量：
-
最后二位数字不能组合成字母：最后一位数字只有一种可能(
0~9可以组合成一种字母)，利用分步计数乘法原理，总共有dp[i-1]*1种可能。 -
最后二位数字可以组合成字母：最后两位数字只有一种可能(
10~25可以组合成一种字母)，利用分步计数乘法原理，总共有dp[i-2]*1种可能。
-
状态定义：dp[i] 表示以 xi 结尾的数字的翻译方案数量。
-
状态方程：
-
初始状态：当
i = 0时，dp[0] = 1。 -
返回值：dp[n]。
class Solution:
def translateNum(self, num: int) -> int:
# a，b分别表示 dp[i-1] 和 dp[i-2]
a = b = 1
pre = num % 10
while num != 0:
num //= 10
cur = num % 10
c = a + b if 10 <= cur*10 + pre < 26 else a
a, b = c, a
pre = cur
return a