计算机程序设计能力考试（PAT）备考通 | PAT模拟样题（难题）

清华计算机学堂 2022-09-10

339

本文将给出一道难题的模拟样题及详解。

难题

1.题目名称：How Many Ways to Decode（35分）

题目描述

Suppose that a string of English letters is encoded into a string of numbers. To be more specific, A-Z are encoded into 0-25. Since it is not a prefix code, the decoded result may not be unique. For example, 1213407 can be decoded as BCBDEAH, MBDEAH, BCNEAH, BVDEAH or MNEAH. Note that 07 is not 7, hence cannot be decoded as H.

Your job is to tell in how many different ways we can decode a numeric string.

输入格式

Each input file contains one test case. Each case occupies a line with a string of no more than 104 digits given with no space.

输出格式

For each test case, print the number of different ways that we can decode the given numeric string. Since the answer might be super large, you only need to output the answer modulo 1000000007.

输入样例

输出样例

解题思路

本题要求将字母 A~Z与数字 0~25对应起来进行编码，将一串给定的数字串解码成字母串。但是这种解码是不唯一的，因为编码不是前缀码（在前缀码中，任何一个字符的编码都不能是其他字符编码的前缀）。

一种直接的思路是从前向后递归推导。首先用 D(1,L)记录解码长度为 L的数字串的不同解决方案的个数，即从第 1个到第 L个数字的解码数。先看第 1个数字，如果是 1，或者是 2且第 2个数字小于 6，则前两个数字一定是某个字母的编码，同时第 1个字母肯定可以独立解码为另一个字母。此时可以先将第 1个字母独立解码，再继续解码剩下的数字串——这种解码的个数是 D(2,L)；然后将前两个数字解码为另一个字母，再继续解码剩下的数字串 ——这种解码的个数是 D(3,L)。于是就有 D(1,L)=D(2,L)+ D(3,L)，可以用一个非常简单的递归函数实现，终止条件为 D(L – 1,L)=1或 2,D(L,L)=1。

下面看一下这个递归算法的时间复杂度，图 4.1给出了 D(1,6)在递归中涉及的所有计算。

■ 图 4.1 D(1,6)的递归计算示意

可以看到，这个计算的流程和计算斐波那契数的递归非常相似，而后者的计算复杂度是指数级的。注意：各个子问题都被重复计算了很多遍，这就意味着动态规划算法该登场了。

动态规划的思路和递归的思路相反向，为了避免重复计算，最好自底向上进行计算，并且将一路上计算过的值都存下来，下次调用时就可以直接取值，不必重新计算了。代码 4.17就是动态规划版本的解。将数字串存在 NumStr中，用数组 dp记录子问题的解，令 dp[i]记录从第 i位到最后一位 dp[L – 1]（数组下标是从 0到 L – 1的）的解码数。显然最后一位数字只有一种解码方法，于是 dp[L – 1]=1；而倒数第 2位数字对应的 dp[L – 2]只有两种可能：首先是倒数第 2位数字肯定可以被解码成一个字母；其次是如果最后两位数字还能解码成另一个字母，那么就多了一种解码方法，即 dp[L – 2]=2；如果最后两位数字不能解码，则 dp[L – 2]=1。用类似的思路从中间的任何一个位置 i看，都容易推出以下两种可能：

如果 NumStr[i]和 NumStr[i+1]可以组成一个字母，则可以先解码 NumStr[i]，再用 dp[i+1]种方法解码从 NumStr[i+1]开始的子串；随后解码 NumStr[i]和 NumStr[i+1]，再用 dp[i+2]种方法解码从 NumStr[i+2]开始的子串，这时 dp[i]=dp[i+1]+dp[i+2]；

如果 NumStr[i]和 NumStr[i+1]无法组成一个字母，则只需要解码 NumStr[i]，再用 dp[i+1]种方法解码从 NumStr[i+1]开始的子串，这时 dp[i]=dp[i+1]。

因为算法是从最后两个 dp值开始倒推的，所以当需要计算 dp[i]时， dp[i+1]和 dp[i+2]都应该已经被计算出来了，这样就避免了重复计算。最后推出来的 dp[0]就是需要的结果。

测试要点

样例给出了一般正确性测试，其他测试数据应至少覆盖长度为 0、1、 2的字符串，以及最长 10⁴位的仅由 1和 2组成的字符串，当然，最长随机字符串也是需要的。

源代码 (C)