面试题46：把数字翻译成字符串

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

思路：
本道题目用到自下而上的递归，动态规划的思想，从右向左得出能翻译的可能性，具体的思路如下：

46 把数字翻译成字符串.png

代码实现：

class Solution:
    def getTranslationCount(self, number):
        """
        :type number: int
        :rtype: int
        """
        if number < 0:
            return None

        str_number =  str(number)
        length = len(str_number)
        counts = [0]*length
        count = 0               #临时变量

        for i in range(length-1,-1,-1):  #从右到左遍历、
            # 先给count赋值上一次遍历的结果
            if i < length-1:
                count = counts[i+1]
            else:
                count = 1

            #实现递归公式f(r) = f(r+1) + g(r,r+1)f(r+2)
            if i < length-1:
                digit1 = int(str_number[i])
                digit2 = int(str_number[i+1])
                digit = 10*digit1 + digit2
                if digit >=10 and digit <=25:
                    if i < length -2:   #倒数第二位之前
                        count += counts[i+2]
                    else:
                        count +=1

            counts[i] = count   #将结果赋值给当前索引的counts列表
        return counts[0]

提交结果：

leetcode结果