题目描述

Alice 和 Bob 需要互相发送秘密消息，并讨论如何编码他们的消息：

• Alice："我们用一个非常简单的编码方式：将 'A' 编码为 $1$，'B' 编码为 $2$，依此类推，直到 'Z' 编码为 $26$。"
• Bob："这个编码太简单了，Alice。比如我发送单词 'BEAN'，编码为 25114，你可能会有多种解码方式！"
• Alice："确实有多种解码方式，比如 'BEAAD'、'YAAD'、'YAN'、'YKD' 和 'BEKD'，但你应该能找出正确的解码。而且你为什么要发送 'BEAN' 呢？"
• Bob："好吧，也许这个例子不太好，但如果给你一个长度为 $500$ 的数字串，解码方式会非常多，甚至可能有两种不同的解码方式都能组成有意义的单词。"
• Alice："到底有多少种解码方式？"
• Bob："天文数字！"

Alice 仍然不相信 Bob 的说法，因此她需要一个程序来计算给定数字串的可能解码方式数量。

输入格式

• 输入包含多组数据，每组数据为一行数字，表示一个有效的加密串（不会以 $0$ 开头）。
• 数字之间没有空格。
• 输入以单独一行 0 结束，该行不需要处理。

输出格式

对于每组输入，输出该数字串的可能解码方式数量。所有答案保证在 long 变量范围内。

样例输入

25114
1111111111
3333333333
0

样例输出

6
89
1

解题思路

关键观察

1. 编码规则：数字 $1$ 到 $26$ 分别对应字母 'A' 到 'Z'。
2. 解码方式：
   • 单个数字（$1$ 到 $9$）可以解码为一个字母。
   • 两个数字（$10$ 到 $26$）也可以解码为一个字母。
3. 动态规划：
   • 设 $dp[i]$ 表示前 $i$ 个数字的解码方式数量。
   • 递推关系：
     • 如果第 $i$ 个数字不为 $0$，则 $dp[i] += dp[i-1]$（单独解码）。
     • 如果第 $i-1$ 和 $i$ 个数字组成的两位数在 $10$ 到 $26$ 之间，则 $dp[i] += dp[i-2]$（组合解码）。

算法步骤

1. 初始化：$dp[0] = 1$（空串有一种解码方式）。
2. 遍历数字串：
   • 检查当前数字是否能单独解码（$1$ 到 $9$）。
   • 检查前两个数字是否能组合解码（$10$ 到 $26$）。
3. 返回结果：$dp[n]$，其中 $n$ 是数字串长度。

代码实现（C++）

#include <stdio.h>
int main(void)
{
	char data[10000];
	int temp[10000];
	int i=0;
	while(scanf("%s",data)&&!('0'==data[0]&&0==data[1]))
	{
		for(i=0;0!=data[i];++i);
		temp[i]=1;
		if('0'==data[i-1])
		{
			temp[i-1]=0;
		}
		else
		{
			temp[i-1]=1;
		}
		for(i-=2;i>=0;--i)
		{
			if('0'==data[i])
			{
				temp[i]=0;
			}
			else
			{
				temp[i]=temp[i+1];
				if('1'==data[i]||'2'==data[i]&&'7'>data[i+1])
				{
					temp[i]+=temp[i+2];
				}
			}
		}
		printf("%d\n",temp[0]);
	}
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数字串长度。
• 空间复杂度：$O(n)$，用于存储 $dp$ 数组。

示例解释

• 输入 25114：
  • 解码方式："BEAAD"、"YAAD"、"YAN"、"YKD"、"BEKD"、"BEAN"，共 $6$ 种。
• 输入 1111111111：
  • 所有数字均为 $1$，可以任意组合，共 $89$ 种解码方式（斐波那契数列）。
• 输入 3333333333：
  • 只能拆分成单个 $3$，对应 'C'，因此只有 $1$ 种解码方式。