本文主要是介绍剑指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.把数字翻译成字符串（动态规划）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
