题目: 给定一个数字,我们按照如下规则把它翻译为字符串:0翻译成”a”,1翻译成”b”,……,11翻译成”l”,……,25翻译成”z”。一个数字可能有多个翻译。一个数字有多少种不同的翻译方法。
此题是一个递归问题。递归式为:f(i)=f(i-1)+g(i)*f(i-2)。当最后两个数字在10到25之间g(i)才等于1。由于有重叠子问题,可以考虑用动态规划,自底向上求解。此题与青蛙跳台阶类似,难点在于判断g(i)哪时候等于1.
参考代码
/** * 把数字翻译成字符串,共有多少种翻译方案 */ public class NumInString { public int getTranslationCount(int number){ if (number<0) return 0; else return getTranslationCount(Integer.toString(number)); } public int getTranslationCount(String number){ char[] numberarray=number.toCharArray(); int[] counts=new int[number.length()];//储存第i个数时,共有多少种翻译方案 for (int i = 0; i <number.length() ; i++) { if (i==0) counts[i]=1; if (i==1) { counts[i]=1; int temp=numberarray[i]-'0'+(numberarray[i-1]-'0')*10; // 前两位也可以用一个字符表示 if (temp>=10&&temp<=26){ counts[i]+=1; } } if (i>1){ counts[i]=counts[i-1]; int temp=numberarray[i]-'0'+(numberarray[i-1]-'0')*10; // 前两位也可以用一个字符表示 if (temp>=10&&temp<=25){ counts[i]+=counts[i-2]; } } } return counts[number.length()-1]; } public static void main(String[] args){ int number=-1; NumInString numInString=new NumInString(); System.out.println(numInString.getTranslationCount(number)); } }