来源：牛客网
已知摩尔斯电码和字符映射关系如下：

• A -> 0
• B -> 1
• C -> 10
• D -> 11
• E -> 100
• F -> 101
• G -> 110
• H -> 111
  当前我们获取到了一串01数字字符串，需要进行摩尔斯电码解码，请问共有多少种解码方法？

输入描述:

一行由0和1组成的字符串

输出描述:

一行一个数字表示答案，即解码方法数量

示例1
输入

11

输出

2

说明

有D和BB两种解法

示例2
输入

100

输出

3

说明

有E,BAA和CA三种解法

备注：

输入字符串长度范围为1～100
输出解码方法数不超过2147483647

解法

这道题有两种解法：

动态规划

这道题是典型的动态规划；维护一个数组dp，代表从这个位置出发到结尾一共有多少种不同的方法；

function safePlus(num1,num2){
    if(num1 > Math.pow(2,31) || num2 > Math.pow(2,31)){
        return (num1 % Math.pow(2,31) + num2 % Math.pow(2,31)) % Math.pow(2,31);
    } else {
        return (num1 + num2) % Math.pow(2,31);
    }
}

process.stdin.resume();
process.stdin.setEncoding('utf-8');
let input = '';
process.stdin.on('data', (data) => {
    input += data;
})
process.stdin.on('end', () => {
    const inputArray = input.split('\n');
    const nums = inputArray[0].split('');
    const n = nums.length;
    // 动态规划
    const dp = new Array(n+1).fill(0);
    dp[n] = 1; // 最后一个字符只能有一种翻译
    for(let i = n - 1; i >= 0; i--){
        dp[i] = dp[i + 1];     // 单字符码的情况
        if(nums[i] === '1'){      // 对于"1"，还有双字符码和三字符码的情况
            if(i + 2 <= n) dp[i] = safePlus(dp[i],dp[i+2]);
            if(i + 3 <= n) dp[i] = safePlus(dp[i],dp[i+3]);
        }
    }
    console.log(dp[0]%(Math.pow(2,31)));
})

记忆化dfs

我们最终要求的答案就是，从数组的0号位置出发，有多少种解码法，它可以被转化成n个子问题：对于i(0 <= i < n ),从数组的第i号出发能有多少种解码法，i可以从i+1、i+2、i+3推断出来。记忆化dfs相当于是一个反向的动态规划dp。
遍历数组，我们维护一个memo数组，memo[i]代表从i出发有多少种解码方法；

每遍历一个位置i，会有两种情况：

1. nums[i] === 0，那么它只有单字符串的解码方法(即解析成A)；
2. nums[i] === 1，那么它有三个分支：单字符串解析(1，即解析自身)，两字符串解析(1x)，三字符串解析(1xx)，所以memo[i+1]=memo[i+1]，memo[i+2]，memo[i+3]。如果对应的memo项已经计算过了，那么直接拿来用(记忆化的精髓，避免计算重复分枝)；否则递归调用dfs函数计算它，这样下一次遇到就直接用；

function safePlus(num1,num2){
	/*因为题目要求输出解码方法数不超过2147483647，所以这里对结果要进行取模运算*/
    if(num1 > Math.pow(2,31) || num2 > Math.pow(2,31)){
        return (num1 % Math.pow(2,31) + num2 % Math.pow(2,31)) % Math.pow(2,31);
    } else {
        return (num1 + num2) % Math.pow(2,31);
    }
}

process.stdin.resume();
process.stdin.setEncoding('utf-8');
let input = '';
process.stdin.on('data', (data) => {
    input += data;
})
process.stdin.on('end', () => {
    const inputArray = input.split('\n');
    const nums = inputArray[0].split('').map((v) => parseInt(v));
    const n = nums.length;
    // 记忆化dfs
    const memo = new Map(); // 表示从这里出发有多少解
    function dfs(pos){
        //console.log('in',pos);
        if(pos === n-1 || pos === n){
            memo.set(pos,1);
            return 1;
        }
        let count = 0;
        while(pos < n && nums[pos] === 0){pos++}; // 0 只有一种解法
        for(let i = 1; i <= 3; ++i){
            if(pos + i > n) break;
            if(memo.has(pos+i)){
                count = safePlus(memo.get(pos+i),count);
            } else {
                count = safePlus(dfs(pos+i),count);
            }
        }
        memo.set(pos,count === 0 ? 1 : count);
        return count === 0 ? 1 : count;
    }
    console.log(dfs(0) % Math.pow(2,31));
})

关于javascript计算精度

这道题要求输出解码方法数不超过2147483647。2147483647 是什么呢？ 是int型(32位)的最大正值，也就是说我们输出的答案要对2^31取模。前面的两种解法里都定义了一个safePlus函数，保证dp数组里的数都不超过2147483647。

这里有2个疑问：

1. JS没有int型限制，为什么在计算过程中每一次都要严格保证这个上限呢？

JS 遵循IEEE 754规范，number类型采用双精度存储（double precision），占用 64 bit，理论上最大正整数应该是2^63 - 1 = 9,223,372,036,854,775,807，远高于这道题所涉及到的正整数。所以理论上，只要最后输出的结果对2^31取模就可以了。

但这种想法忽略了JS的精度问题。

事实上，由于采用双精度存储（double precision），JS的整数存在精度上下限：上下限为+= 2^53 - 1

console.log(Number.MAX_SAFE_INTEGER)  // 9007199254740991 ；
console.log(Number.MIN_SAFE_INTEGER)  //-9007199254740991

在计算最终答案的过程中，部分测试用例就已经超过Number.MAX_SAFE_INTEGER了，这意味着在计算dp数组的过程中已经发生了精度丢失。所以如果只对最后的计算结果取模，答案必然是错误的。因此我们需要在运算的每一步中都做取模运算。

2. 为什么取模的时候要对加数也取模？

在每一次加法的时候，safePlus函数是这么写的：

function safePlus(num1,num2){
	/*因为题目要求输出解码方法数不超过2147483647，所以这里对结果要进行取模运算*/
    if(num1 > Math.pow(2,31) || num2 > Math.pow(2,31)){
        return (num1 % Math.pow(2,31) + num2 % Math.pow(2,31)) % Math.pow(2,31);
    } else {
        return (num1 + num2) % Math.pow(2,31);
    }
}

这里应用了取模的一个性质:

(a + b) % c = (a % b + b % c) % c

之所以用这个性质，是因为加数num1+num2有可能超过Number.MAX_SAFE_INTEGER，即丢失精度，这时候再对它取模为时已晚，得到的还是错误的答案。所以要用到上面的性质，对加数也取模。

一个槽点

众所周知，java和C++里超出2147483647的int型，数值位会溢出到符号位，也就是会变成负数，综上所述也是要在运算的时候不断取模才能避免输出一个负数的答案；但我在解题区没有发现做这个特殊处理的，清一色的都把dp数组设成了int[]。

例如这个答案：

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] str = br.readLine().toCharArray();
        int n = str.length;
        int[] dp = new int[n + 1];
        dp[n] = 1;         // 最后一个字符肯定只能是一种翻译
        // 从后往前遍历字符
        for(int i = n - 1; i >= 0; i--){
            dp[i] = dp[i + 1];     // 单字符码的情况
            if(str[i] == '1'){      // 对于"1"，还有双字符码和三字符码的情况
                if(i + 2 <= n) dp[i] += dp[i + 2];
                if(i + 3 <= n) dp[i] += dp[i + 3];
            }
        }
        System.out.println(dp[0]);
    }
}

它可以通过所有的测试用例，但并不代表它是没有问题的。例如这个输入：
0111101001100001110111100010011111111110001001101111111001011100000101010011010101101000101111111100100101111110011
跑上面的solution得到的结果是：
-2057468566

巧就巧在所有的测试用例都避免了这种情况；

这里吐槽一下：
网易你确定这是前端开发工程师的考试？