运行该程序将得到以下输出：

Keypad #1:
1: A
2: BCDE
3: FGHI

算法分析

使用上一节的输入数据运行该程序，主要的运行状态如下所示：

上述程序中：

• K 是按键的个数。L 是要分配到各个按键中的字符的个数。T 是测试案例的个数。一维数组 F 的大小为 L，保存各个字符出现的频率。
• cost 是大小为 L x L 的二维数组，cost[i][j] 表示第 i 到第 j 个字符分配到某个按键上的代价，即输入这 j - i + 1 个字符(乘上它们出现的频率)的总的按键次数。注意，主对角线上的值就是各个字符出现的频率。这体现在源程序中 initialize 函数的第 12 到第 14 行。初始化之后，cost 的数组的值就不再改变了。
• price 是大小为 K x L 的二维数组，price[i][j] 表示前 j 个字符分配在前 i 个按建上的最小代价。上图中的 A 的值是大约是 INT_MAX 的一半。第一个字符一定是分配在第一个按键上的，而不管第一个字符出现的频率如何(实际上第一个字符的频率可以设置为任何正数，而不影响程序的运行结果)。所以 price[0][0] 初始化设置为 0，而 price 数组的其他值初始化为一个比较大的数。 
• index 是大小为 K x L 的二维数组，index[K][L] 表示第 K 个(最后一个)按键上分配的字符数，然后往回倒算，index[K - 1][L - index[K][L]] 表示第 K - 1 个按键上分配的字符数，... 一直倒算到第 1 个按键为止。这体现在源程序第 28 到 35 行的 output 函数中，使用递归是为了以正确的顺序输出这些按键。
• 程序中最关键的是第 17 到第 26 行的 compute 函数。该函数通过三重循环将问题分角为子任务用动态规划算法求解。子任务是求将 j 个字符分配到 i 个按键上的最小代价。
• 第 19 行：i 从 1 到 K 循环逐步求解。总共有 K 个按键。
• 第 20 行：j 从 i 到 L 循环逐步求解。总共有 L 个字符，且每个按键至少必须分配一个字符。
• 第 21 行：n 从 1 到 j - i + 1 逐步求解。注意，这里 n 是指最后一个按键中分配的字符数。
• 第 23 行：这是最关键的计算最小代价的公式，sum 由两部分组成，第二部分是将第 j - n + 1 到第 j 个字符(总共 n 个)分配到第 i 个按键(也就是该子任务中的最后一个按键)中的最小代价，第一部分就是将该子任务中剩下的 j - n 个字符分配到前 i - 1 个按键中的最小代价。注意，该子任务总共要分配 j 个字符。
• 第 24 行：如果计算出来的最小代价比原来的小，就更新最小代价数组 price，并同时更新 index 数组，以便将来输出键盘布局。
• 三重循环完成，表明整个计算任务完成，L 个字符已经分配到 K 个按键中。此时，price[K][L] 表示所求的最小代价，在我们例子中就是 246。

注意，这道题目要求在同等代价下将字符尽量分配到后面的按键中，所以第 24 行比较代价时使用“<=”，以便尽量增加后面按键的字符数。 如果将这个程序第 24 行的“<=”改为“<”，则将得到以下输出：

Keypad #1:
1: ABC
2: DE
3: FGHI

此时，策略是在同等代价下将字符尽量分配到前面的按键中。

英语国家手机数字键盘的最优方案

维基百科网站的 Letter frequency 给出了英语中二十六个字母出现的频率，如下表所示：

根据上表设置相应的输入文件：

1
8 26
23456789
ABCDEFGHIJKLMNOPQRSTUVWXYZ
8167
1492
2782
4253
12702
2228
2015
6094
6966
153
772
4025
2406
6749
7507
1929
95
5987
6327
9056
2758
978
2360
150
1974
74

运行结果如下所示：

Keypad #1:
2: AB
3: CD
4: EFG
5: HIJK
6: LM
7: NOPQ
8: RS
9: TUVWXYZ

数字“9”键上居然有七个英文字母，可见最后几个英文字母出现的频率很低。看来在英文国家手机的数字键盘应该如上设置才能够更好地输入信息。当然，我们输入中文又是另外一回事了，用拼音和用五笔输入法，各个字母的频率也是不同的。其实手机向智能化发展，越来越多地使用全键盘了，不再使用数学小键盘。

更好的算法

我的 C 程序在 SPOJ 网站上提交的结果如下所示：

也就是说我的程序运行时间是 0.57 秒，但是这道题目前最好的运行时间是 0.21 秒：

这肯定有更好的算法。有哪位园友知道更好的算法，请在评论中告诉我。谢谢！

算法和数据结构目录