题目

给定一个数字，按照如下规则把他翻译成字符串，0翻译成a,1翻译成b,……….11 翻译成l，25翻译成z,这样一个数字可能有多种翻译方式，请计算一个数字有多少种翻译的方法。

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int transfer(int number)
{
    string numberstring =to_string(number);
    int mysize =numberstring.size();
    int* dp = new int[mysize];
    dp[mysize]=0;
    dp[mysize-1]=1;
    int g =0;
    for(int i=mysize-2;i>=0;i--)
    {
        int digit1 = numberstring[i]-'0';
        int digit2 = numberstring[i+1]-'0';
        int covered =digit1*10+digit2;
        if(covered>=10&&covered<=25)
        {
            g=1;
        }
        else g =0;
        dp[i]= dp[i+1]+g*dp[i+2];
    }
    return dp[0];
}

思路

一道简单的动态规划题，从前往后算会算很多重复的数字，所以选择从后往前算避免重复的数字，

自下而上，动态规划，从最小的问题开始 ：
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

对于12258 ，其中的258 来说，到2的时候，f(2) 有25+8(即 1 * f(4) ) 和2 +58(即 f(3) ).