题目

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法

示例

  1. 输入: 12258
  2. 输出: 5
  3. 解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

解析

  1. function transNum (num) {
  2.     const str = num + ''
  3.   const arr = new Array(str.length).fill(1)
  5.   for (let i = 1, iLen = arr.length; i < iLen; i++) {
  6.       let temp = Number(str[i - 1] + str[i])
  8.     if (10 <= temp && temp <= 25) {
  9.       arr[i] = arr[i - 1] + (i === 1 ? 1 : arr[i - 2])
  10.     } else {
  11.         arr[i] = arr[i - 1]
  12.     }
  13.   }
  15.   return arr
  16. }

思路：
设数组 dp []，数据长度等于传入数字转为字符串的长度，全部填充为 0
假设截止到第 i 个数字，翻译的方法是 dp[i]，显而易见，dp[0] = 1

那么对于索引 i 不为 0 的字符，dp[i] 就拥有两个情况

  1. 一个是当前的数字可以和前一个数字进行翻译，也就是属于 [0,25] ，那么 dp[i] = dp[i -1] + dp[i -2]
  2. 如果当前的数字不可以和前一个数字进行翻译，那么 dp[i] = dp[i - 1]

动态规划：
状态定义 — dp[i] 代表第 i 个数字的翻译数量

转移方程：
一个是当前的数字可以和前一个数字进行翻译，也就是属于 [0,25] ，那么 dp[i] = dp[i -1] + dp[i -2]
如果当前的数字不可以和前一个数字进行翻译，那么 dp[i] = dp[i - 1]

初始状态：dp[0] = dp[1] = 1，就是“无数字”和只有一个数字的情况，只有一个翻译方法

参考链接

剑指 offer 46 把数字翻译成字符串（动态规划）