摩尔斯电码解码

[编程题]摩尔斯电码解码

热度指数：3607 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

已知摩尔斯电码和字符映射关系如下：

A -> 0

B -> 1

C -> 10

D -> 11

E -> 100

F -> 101

G -> 110

H -> 111

当前我们获取到了一串01数字字符串，需要进行摩尔斯电码解码，请问共有多少种解码方法？

输入描述:

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

输出描述:

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

示例1

输入

输出

说明

有D和BB两种解法

示例2

输入

输出

说明

有E,BAA和CA三种解法

备注:

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

算法知识视频讲解

牛客372475258号

发表于 2021-01-20 00:36:10

解析到第i个字符时，如果第i个字符单独解析则有dp[i-1]种解析方式如果第i个字符与i-1个字符一起解析，则需要i-1字符不为0，如果与i-1,i-2一起解析，则要求i-2字符不为0;所以解析到第i个字符的数量dp[i]=dp[i-1]+dp[i-2](能同时解析的数量)+dp[i-3](能同时解展开全文

大厂算法岗必拿下

发表于 2021-09-16 05:42:10

分为 1 位， 2位， 3位。然后从底向高位逐渐添加。 dp[0] = 1是由动态规划方程给出来的。三种情况，先走1，再走2，最后走3.dp[i] = dp[i-1]; dp[i] += dp[i-2];dp[i] += dp[i-3]; 记得对long long 最大值取余。214748364 展开全文