题目链接
思路
- 示例:12258有5种不同的翻译,分别是"bccfi",“bwfi”,“bczi”, “mcfi"和"mzi”
- 对于12258来说;1225可以是12+c+f也可以是12+z;
- 动态规划:dp[i]以第i个数字结尾的当前数字串拥有之前的数字串的方法数
- 如果相邻的两个数字组成大于等于10并且小于等于25的数;dp[i] = dp[i-1]+dp[i-2]
- 如果相邻的两个数字组成小于10或者大于25的数;dp[i] = dp[i-1]
java
public int translateNum(int num) {
int res = 1;
int dp = 1;
int ge = num % 10;
while (num != 0) {
num /= 10;
int shi = num % 10;
int i = shi * 10 + ge;
int current;
if (i >= 10 && i <= 25) {
current = res + dp;
} else {
current = res;
}
dp = res;
res = current;
ge = shi;
}
return res;
}
go
func translateNum(num int) int {
res, dp, ge := 1, 1, num%10
for num != 0 {
num /= 10
shi := num % 10
i := shi*10 + ge
var current int
if i >= 10 && i <= 25 {
current = dp + res
} else {
current = res
}
dp = res
res = current
ge = shi
}
return res
}
|