时间： 2019-07-02
题目链接：Leetcode
tag： 动态规划
难易程度：中等
题目描述：
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
示例:
输入: 12258 输出: 5 解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"提示
1. 0 <= num < 2^31本题难点
当数字中包含两位数时，存在两种不同的组合情况。
具体思路
动态规划： num = x 1 x 2 … x i − 2 x i − 1 x i … x n − 1 x n (例如 : 12258 = x 1 x 2 x 3 x 4 x 5 ) [ 设 x 1 x 2 … x i − 2 的翻译方案数量为 f ( i − 2 ) 设 x 1 x 2 … x i − 2 x i − 1 的翻译方案数量为 f ( i − 1 ) \begin{array}{l} \text { num }=x_{1} x_{2} \ldots x_{i-2} x_{i-1} x_{i} \ldots x_{n-1} x_{n} \\ \text { (例如 }\left.: \quad 12258=x_{1} x_{2} x_{3} x_{4} x_{5}\right) \\ \\ {\left[\begin{array}{l} \text { 设 } x_{1} x_{2} \ldots x_{i-2} \text { 的翻译方案数量为 } f(i-2) \\ \text { 设 } x_{1} x_{2} \ldots x_{i-2} x_{i-1} \text { 的翻译方案数量为 } f(i-1) \end{array}\right.} \end{array} num =x1x2…xi−2xi−1xi…xn−1xn (例如 :12258=x1x2x3x4x5)[ 设 x1x2…xi−2 的翻译方案数量为 f(i−2) 设 x1x2…xi−2xi−1 的翻译方案数量为 f(i−1)
{ 当整体翻译 x i − 1 x i 时, x 1 x 2 … x i − 2 x i − 1 x i 的方案数为 f ( i − 2 ) 当单独翻译 x i 时, x 1 x 2 … x i − 2 x i − 1 x i 的方案数为 f ( i − 1 ) \left\{\begin{array}{ll} \text { 当整体翻译 } x_{i-1} x_{i} \text { 时, } & x_{1} x_{2} \ldots x_{i-2} x_{i-1} x_{i} \text { 的方案数为 } f(i-2) \\ \text { 当单独翻译 } x_{i} \text { 时, } & x_{1} x_{2} \ldots x_{i-2} x_{i-1} x_{i} \text { 的方案数为 } f(i-1) \end{array}\right. { 当整体翻译 xi−1xi 时, 当单独翻译 xi 时, x1x2…xi−2xi−1xi 的方案数为 f(i−2)x1x2…xi−2xi−1xi 的方案数为 f(i−1)
递推关系： f ( i ) = { f ( i − 2 ) + f ( i − 1 ) , 若数字 x i − 1 x i 可被翻译 f ( i − 1 ) , 若数字 x i − 1 x i 不可被翻译 f(i)=\left\{\begin{array}{cc} f(i-2)+f(i-1) & , \text { 若数字 } x_{i-1} x_{i} \text { 可被翻译 } \\ f(i-1) & , \text { 若数字 } x_{i-1} x_{i} \text { 不可被翻译 } \end{array}\right. f(i)={f(i−2)+f(i−1)f(i−1), 若数字 xi−1xi 可被翻译 , 若数字 xi−1xi 不可被翻译
d p [ i ] = { d p [ i − 1 ] + d p [ i − 2 ] , 10 x i − 1 + x i ∈ [ 10 , 25 ] d p [ i − 1 ] , 10 x i − 1 + x i ∈ [ 0 , 10 ) ∪ ( 25 , 99 ] d p[i]=\left\{\begin{array}{ll} d p[i-1]+d p[i-2] & , 10 x_{i-1}+x_{i} \in[10,25] \\ d p[i-1] & , 10 x_{i-1}+x_{i} \in[0,10) \cup(25,99] \end{array}\right. dp[i]={dp[i−1]+dp[i−2]dp[i−1],10xi−1+xi∈[10,25],10xi−1+xi∈[0,10)∪(25,99]
注意：dp[0]=dp[1]=1 ，即 “无数字” 和 “第 1 位数字” 的翻译方法数量均为 1
复杂度分析：
时间复杂度 O(N) ： N 为字符串 s的长度（即数字 num 的位数 log(num)），其决定了循环次数。空间复杂度 O(N) ： 字符串 s使用 O(N) 大小的额外空间。解题思路
利用求余运算 num%10 和求整运算 num/10 ，可获取数字 num 的各位数字（获取顺序为个位、十位、百位…）。因此，可通过 求余 和 求整 运算实现 从右向左 的遍历计算。动态规划 “对称性” ，可知从右向左的计算是正确的。
代码
class Solution { public int translateNum(int num) { int a = 1, b = 1, x, y = num % 10; while(num != 0) { num /= 10; x = num % 10; int tmp = 10 * x + y; int c = (tmp >= 10 && tmp <= 25) ? a + b : a; b = a; a = c; y = x; } return a; } }