[原创]【动态规划求解“键盘上字母分配”问题】

随着手机的普及,手机短信的交流方式也越来越流行(注:此处的短信主要指的是英文短信)。如下图1,就是标准手机键盘上用来打出26个字母(a~z)的按键布局。由于每个键上有多个字母,我们打字时常会遇到的情况是,某些常用字母可能需要按几下键才能打出来。比如字母“s”,需要按四次键才能选中。如果我们把字母按照图2的方式分配到各个按键上,那么打字就会方便一些,因为只要按两次键就可以选中“s”,虽然打出p、q需要的按键次数增加了,但是在英文中p、q的出现的频率比“s”小的多,于是这样做总的来说是值得的。