c# - 通过键盘按下输入文本的最短路径

Question

我从用户那里得到自定义字符串。现在我需要设计在包含 9 个按钮的键盘中按下此字符串的最短路线。

注意:

• 解决方案字母应按字母顺序排列，即 a、b、c、d、e、...
• 每个号码至少包含一个键盘字符

if input text = 'hello' 的解决方案

1. a, b, c, d
2. e, f, g
3. h, i, j, k
4. l, m, n
5. o, p, q
6. r, s, t
7. 你，你，你
8. x,y
9. z

或者

1. a, b, c, d
2. e, f, g
3. h, i, j, k
4. l, m, n
5. o
6. p
7. 问
8. r
9. s, t, u, v, w, x, y, z

使用这个键盘，我需要按 3、2、4、4、5 来输入“你好”

因此，如果您想使用这种设计的键盘输入“你好”，您只需按下键盘上的 5 个按钮，因为这是最少的键数。

我认为这道题是用贪心法或者回溯算法来解决的。

Answer 1

让我们将字母表概括为 {1, …, n}。令 k 为键的数量。对于 1 ≤ i < j ≤ k，可能的键 {i, …, j} 的成本(= 按下次数)是 1f_i + 2f_i+1 + … + (j - i + 1) f_j，其中 f_i 是字母 i 的频率。我们正在寻找恰好包含 k 个键的最小成本精确覆盖。

此问题具有以下最优子结构:修复任意最优解并删除带有 {m + 1, …, n} 的 key 。结果是具有 k - 1 个键和字母表 {1, …, m} 的问题的最优解；否则，我们可以通过重新排列前 k - 1 个键来改进第一个最优解。

据此，我们可以应用动态规划。对于每个 0 ≤ i ≤ n 和每个 0 ≤ j ≤ k，计算具有 j 个键的 {1, …, i} 的最优排列。这种安排的代价C_i,j满足递归

C_0,j = 0 对于所有 j ≥ 0
C_i,0 = ∞ 对于所有 i > 0
C_i,j = min_{0 ≤ i' < i} (C_i',j-1 + c_i',j ),

其中 c_a,b 是 key {a, …, b} 的成本。可以从最优参数序列 i' 中恢复排列本身。