题目描述
解析思路
leetcode 中国中的一个中等难度面试题——把数字翻译成字符串，是一个较为简单的动态规划问题(虽然简单我也不会呀)。
咋一看这个题目描述是懵逼的，思考 10 分钟无果，果断看了解题思路，豁然开朗。
假设数字的长度为nn，第ii个数为xixi,长度为nn的数字结果为f(n)
我们开始找规律：
- n=0n=0时,f(0)=1f(0)=1
- n=1n=1时,f(1)=1f(1)=1
- n=2n=2时,f(2)=2f(2)=2
- n=3n=3,假设前两位是 12
当第三位能和 2 合体时（比如为 5），我们可以把 25 当作一个组合，剩余数字f(1)f(1)的结果就是此种情况下的结果数。另外一种情况是将 5 作为一个组合，剩余数字f(2)f(2)的结果为此种情况下的结果数。总的为f(1) f(2)f(1) f(2)
当第三位不能和第二位合体（比如 8），就只能将 5 作为一个整体，此种情况下的结果为f(2) . .
- 依次类推，能得到如下这样一个推导式：
思考为什么能得到上面的推导式：
- 当一串数字 n 加一个数字的时候，如果这个数字不能和前一个数字组成一个整体，那么实际上结果数是不变的，还是f(n−1)f(n−1)
- 如果能组成那就分成两种情况，将这个数字单独作为一个整体，那么还是和上面一样结果是f(n−1)f(n−1),两外一种是和前一个数字凑成一个整体，这种情况就相当于长度为 n-2 是加上了一个数字，那么结果就是f(n−2)
综合起来就得到了上面的推导公式
代码(Java 实现)
代码语言：javascript复制/**
* Created with IntelliJ IDEA
*
* @author fanxb
* Date: 2020/6/9 15:10
*/
public class Q46 {
public int translateNum(int num) {
String str = String.valueOf(num);
//a=f(0),b=f(1)
int a = 1, b = 1, sum = 1;
for (int i = 1, length = str.length(); i < length; i ) {
String temp = str.substring(i - 1, i 1);
sum = temp.compareTo("10") >= 0 && temp.compareTo("25") <= 0 ? a b : b;
a = b;
b = sum;
}
return sum;
}
public static void main(String[] args) {
System.out.println(new Q46().translateNum(12258));
}
}
