把数字翻译成字符串

题目：

​ 给定一个数字，我们按照如下规则把它翻译为字符串：0翻译成"a"，1翻译成"b"，……，11翻译成"l"，……，25翻译成"z"。一个数字可能有多个翻译。例如12258有5种不同的翻译，它们分别"bccfi", "bwfi", "bczi", "mcfi" 和"mzi" 。请编程实现一个函数用来计算一个数字有多少种不同的翻译方法。

分析

自上而下，从最大的问题开始，递归 ：

             12258
          /          \
       b+2258        m+258
        /   \        /    \
    bc+258 bw+58  mc+58  mz+8
   	  /  \     \      \     \
  bcc+58 bcz+8 bwf+8  mcf+8  mzi
    /      \     \      \
 bccf+8   bczi  bwfi    mcfi
  /
bccfi
有很多子问题被多次计算，比如258被翻译成几种这个子问题就被计算了两次。
自下而上，动态规划，从最小的问题开始 ：

f(r)表示以r为开始（r最小取0）到最右端所组成的数字能够翻译成字符串的种数。对于长度为n的数字，f(n)=0,f(n-1)=1,求f(0)。
递推公式为 f(r-2) = f(r-1)+g(r-2,r-1)*f(r)；
其中，如果r-2，r-1能够翻译成字符，则g(r-2,r-1)=1，否则为0。
因此，对于12258：
f(5) = 0
f(4) = 1
f(3) = f(4)+0 = 1
f(2) = f(3)+f(4) = 2
f(1) = f(2)+f(3) = 3 
f(0) = f(1)+f(2) = 5

1. 使用递归：用f(i)来表示从第i位开始的不同翻译数目，可以得到有：f(i)=f(i+1)+g(i,i+1)*f(i+2)。i和i+1位数字拼起来在10~25范围内时g(i,i+1)的值为1，否则为0。
2. 但是存在重复的子问题，所以递归并非最佳方法，我们从数字的末尾开始计算f(i)，自下而上解决问题，就可以消除重复的子问题了。先算f(len-1)，f(len-2)，再根据公式f(i)=f(i+1)+g(i,i+1)*f(i+2)往前逐步推导到f(0)，这就是最终要求的结果。

代码：

public class Solution {

    public int getTranslationCount(int number) {
        if (number < 0) {
            return 0;
        }
        String strNumber = String.valueOf(number);
        int length = strNumber.length();
        int[] counts = new int[length];
        for (int i = length - 1; i >= 0; i--) {
            if (i == length - 1) {
                counts[i] = 1;
            } else {
                counts[i] = counts[i + 1];
                if (canBeTrans(strNumber, i)) {
                    if (i == length - 2) {
                        counts[i] += 1;
                    } else {
                        counts[i] += counts[i + 2];
                    }
                }
            }
        }
        return counts[0];
    }

    private boolean canBeTrans(String strNumber, int i) {
        int a = strNumber.charAt(i) - '0';
        int b = strNumber.charAt(i + 1) - '0';
        int convert = a * 10 + b;
        if (convert >= 10 && convert <= 25) {
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int count = solution.getTranslationCount(123123);
        System.out.println(count);
    }
}