给定一个数字,我们按照如下规则把它翻译为字符串:0 翻译成 “a” ,1 翻译成 “b”,……,11 翻译成 “l”,……,25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数,用来计算一个数字有多少种不同的翻译方法。
分析:
用 dp(i)dp(i) 表示前 ii 个数字的翻译方法数
首先明确状态(显而易见了),接下来明确选择
我们可以有两种选择方式:①就单独排 ②和前面一个组合(前提是组合数得是10-25的)
接下来我们就可以写状态转移方程了
动态规划解法
class Solution { public int translateNum(int num) { //dp[i] 表示前i个数字的翻译方法数。 Integer number=num; String str=number.toString(); int n=str.length(); int dp[]=new int [n+1]; dp[1]=1; for(int i=2;i<=n;i++){ if(str.charAt(i-2)=='1'||(str.charAt(i-2)=='2'&&str.charAt(i-1)<'6')){ if(i==2){ dp[i]=2; }else{ dp[i]=dp[i-1]+dp[i-2]; } }else{ dp[i]=dp[i-1]; } } return dp[n]; } }