把数字翻译成字符串

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

思路：当最开始的一个数字或两个数字翻译成一个字符后，我们接着翻译后面剩下的数字。

显然，可以写一个递归函数来计算翻译的数目。

我们定义函数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,否则g(i,i+1)=0。

递归从最大的问题开始自上而下解决问题，我们也可以从最小的子问题开始自下而上解决问题，这样可以消除重复的子问题。

参考代码：

root@gt:/home/git/Code# ./a.out 5root@gt:/home/git/Code# cat getTransCount.c #include <stdio.h>#include <string.h>#include <stdlib.h>int getNumCount(int num){	int count = 0;	while(num)	{		++count;		num /= 10;	}	return count;}int core(int* nums,int numCount){	int count = 0;	int* counts = (int*)malloc(numCount*sizeof(int));	memset(counts,0,sizeof(int)*numCount);	for(int i = numCount - 1;i >= 0;--i)	{		if(i < numCount - 1)			count = counts[i + 1];		else			count = 1;				if(i < numCount - 1)		{			int digit1 = nums[i];			int digit2 = nums[i + 1];			int converted = digit1 * 10 + digit2;			if(converted >= 10 && converted <= 25)			{				if(i < numCount - 2)					count += counts[i + 2];				else					count += 1;			}		}		counts[i] = count;	}	count = counts[0];	free(counts);	return count;}int getTransCount(int num){	if(num < 0)		return 0;	int* nums = (int*)malloc(10*sizeof(int));	int temp = 0;	memset(nums,'\0',sizeof(&nums));	int numCount = getNumCount(num);	for(int i = 0;i < 10 && num != 0;++i)	{		temp = num % 10;		num /= 10;		nums[numCount - i - 1] = temp;	}	int res = core(nums,numCount);	free(nums);	return res;}int main(){	int res = getTransCount(12258);	printf("%d\n",res);	return 0;}