面试题46.TranslateNumbersintoStringszi-fan-yi-cheng-zi-fu-chuan-lcoftopic给定一个数字，我们按照以下规则将其翻译成字符串：0被翻译成“a”,1翻译成“b”,...,11翻译成“l”,...,25翻译成“z”。一个数字可能有多个翻译。请编写一个函数来计算一个数字有多少种不同的翻译方法。例1：输入：12258输出：5解释：12258有5种不同的译法，分别是“bccfi”、“bwfi”、“bczi”、“mcfi”和“mzi”提示：0<=num<231解题思路：动态编程首先明确题意，题中解释规则：0翻译成“a”，1翻译成“b”，……，25翻译成“z”。标题还写着[一个数字可能有多种翻译]。那么这里可以想一下，当数字大于等于10小于等于25的时候，这部分数字可以看成是两个独立的数字，也可以看成是一个数字。现在看例子1：输入：12258输出：5解释：12258有5种不同的翻译，分别是“bccfi”、“bwfi”、“bczi”、“mcfi”和“mzi”看下面的解释，我们可以看到：”bccfi”这样的话，所有的数字都是分开翻译的，即[1,2,2,5,8]剩下的4个是连续的两位数，可以组合成[1,22,5,8]的对应的翻译是"bwfi"[1,2,25,8]对应的翻译是"bczi"[12,2,5,8]对应的翻译是"mcfi"[12,25,8]对应的翻译是"姆齐”。在上面的示例中，'58'的组合无效。我们知道组合数字的范围应该在[10,25]之间。也就是说翻译的规则在字符串的第i位可以分为两种情况：单独翻译可以和i-1位合起来落入[10,25]，那么就可以连起来了上来翻译。现在假设题目给的数num的第i个记为$x_i$，比如例子中num=12258，那么$x_1$就是1。现在定义动态规划表dp，假设dp[i]是以$x_i$结尾的数字的翻译方案。传递方程是根据前面得到的翻译规则总结出来的。当两个数字$x_{i-1}$和$x_i$的组合可以被翻译时，这里有两种情况。单独翻译，或合并翻译。即：组合翻译时，$x_{i-1}x_i$的组合是确定的，前i-2个数的翻译方案为dp[i-2]。单独翻译时，$x_i$确定前i-1个数字的翻译方案为dp[i-1]。也就是说，当$x_{i-1}$和$x_i$的组合可以平移时，可以将以上两种情况组合起来，最终dp[i]=dp[i-2]+dp[i-1]。如果$x_{i-1}$和$x_i$这两个数不能组合，就只能翻译成一个数。所以dp[i]=dp[i-1]。这里需要注意的可组合数的范围是[10,25]，如前所述，只有这种情况下组合才能翻译成功。还有一种情况，就是当$x_{i-1}$为0时，这种情况下可能会有00,01,02,...等数字的组合。但这种情况是无法翻译的。所以最终的状态转移方程，以及具体区间：$$dp[i]=\begin{cases}dp[i-2]+dp[i-1],&10x_{i-1}+x_i\in[10,25]\\dp[i-1]&10x_{i-1}+x_i\in[0,10)\bigcup(25,99]\end{cases}$$注意这里我们不考虑三位数字的组合这里dp[i]表示以$x_i$结尾的数字的转换方案，当i=0和i=1时，分别表示[没有数字]和[第一个数字]，这里都初始化了为1。（上面解释过，$x_1$表示第一个数，比如12258题中的第一个数1。）反推dp[0]的值，假设当两个数可以合并的情况下，翻译过来，比如12，那么dp[2]显然等于2。以[1,2]形式或[12]形式翻译。此时dp[2]=dp[1]+dp[0]=2，dp[1]为1，则dp[0]=1。最终我们需要得到的结果是dp[n]]，也就是题目中需要的翻译方案（n代表数字的长度。）这里可以使用字符串截取的方法来实现，这里需要对数字进行下转换缺点是字符串会占用一定的空间。这里使用字符串截取的方法来解决问题。另一种方法是使用取模法（可以考虑试试）。具体代码如下。代码实现类解决方案：deftranslateNum(self,num:int)->int:string=str(num)n=len(string)dp=[0]*(n+1)dp[0]=1dp[1]=1foriinrange(2,n+1):if"10"<=string[i-2:i]<="25":dp[i]=dp[i-1]+dp[i-2]else:dp[i]=dp[i-1]returndp[n]实现结果总结一下这道题用到的动态规划，先分析题意，找出翻译规律。可以发现，在翻译第i个数字时，可能会出现两种情况：第i个位置的数字被单独翻译；当第i个位置的数与第i-1个位置的数组合可以平移时，则考虑组合进行平移，根据上述平移规则，可得到传递方程（参考上述分析详解）：当两个连续数可以组合时：dp[i]=dp[i-2]+dp[i-1]否则：dp[i]=dp[i-1]初始化动态规划列表，并且确定最终的解值为dp[n]。
