剑指offer-46.把数字翻译成字符串（动态规划）剑指offer-46.把数字翻译成字符

题目来源：https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

示例 1:
输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

思路：
一开始想说建个哈希方便查找。。看了一下题解，其实是个一维的动归：

状态：dp[i]，表示i个数字最多有多少翻译方法。
状态转移方程：考虑输入为1 2 2 8，那么有三种翻译方法，怎么来的呢？按顺序推：
dp[1]：一个数字，当然是1种
dp[2]：2的前序数字为num[0] = 1，所以2要么和1组合，要么不组合，所以有2种：dp[2] = dp[1] + dp[0]
dp[3]：2的前序数字为2，如果组合的话，组成数字为22，在表示范围内，那么可以选择组合或者不组合，不组合时，2单独翻译，dp[3] = dp[2]，组合时，22组合在一起了，那么dp[3] = dp[1]，所以最终有dp[3] = dp[1] + dp[2]
dp[4]：8的前序数字为2，如果组合的话，组成数字为28，不在表示范围内，所以8只能单独翻译，那么有dp[4] = dp[3]
根据这个过程，可以有如下结论：
dp[i] = dp[i-1] + dp[i-2]if (num[i-2:i] < '26' and num[i-2] == '2') or num[i-2] == '1'
dp[i] = dp[i-1]else
初始化：dp[0]=1, dp[1]=1,所以全部初始化为1就行。

class Solution(object): def translateNum(self, num): """ :type num: int :rtype: int """ num = str(num) n = len(num) dp = [1] * (n+1) for i in range(2, n+1): if num[i-2] == '1' or (num[i-2] == '2' and num[i-2:i] < '26'): dp[i] = dp[i-1] + dp[i-2] else: dp[i] = dp[i-1] return dp[-1]

参考：
https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/solution/46-pythondong-tai-gui-hua-by-lullaby/
【剑指offer-46.把数字翻译成字符串（动态规划）】