最大化以字母r结尾的行数

Question

我想到了一道算法测试中的问题。这个问题是关于一个男孩写文章的，他希望最大化以字母'r'结尾的行数，因为他认为这样会在文章上获得更高的分数（什么...）。

无论如何，文章的限制是每行的最后72-80个字符需要有一个字母，除非包括下一个单词会超过80个字符（例如，如果添加下一个单词会使该行具有80个以上的字符，则可以在72-80个字符位置没有字母的情况下保留该行），或者它是最后一行（最后一行可以少于72个字符）。

例如，如果限制是10-15而不是72-80，那么格式应如下所示：

123456789012345

The slow blue  
dog is  
entertaining

有没有一种高效的算法，可以在保持72-80字母限制的同时最大化以字母“r”结尾的行数？我们不能切割整个单词来使得行以“r”结尾。

我尝试使用的算法如下：

1. 从第72个字符开始，检查当前行的72-80个字符是否包含字母“r”。
2. 如果72-80个字符中没有字母“r”，则尽可能填满该行并转到下一行。
3. 如果72-80个字符中有字母“r”，则结束该行。
4. 重复步骤1直到没有更多的行。

我对这种贪心算法的主要问题是第2步。尽可能填满该行可能会阻止未来以“r”结尾的行。

使用这种10-15的约束条件的算法将得到：

123456789012345
The man was in 
the backgarden  
or the yard

但最佳解决方案应该是：

123456789012345
The man was 
in the 
backgarden or 
the yard

Sorry.

- Andy

---

为什么第二个“最优解”是合法的？如果限制每行10-15个字符，那么“in the”和“the yard”不是非法行吗？ - Benjamin Gruenbaum

如果添加下一个单词会导致行超过15个字符，我们可以在一行上少于10个字符。在这种情况下，添加“后花园”将使第二行长度为17个字符。至于“院子”，你是正确的。我忘了提到最后一行可以少于10个字符。编辑中。 - Andy

@Andy，是否有可能切割整个单词以使行以“r”结尾？另外，每行的最小长度是多少？ - smac89

@Smac89 不可以为了让行以“r”结尾而切割整个单词。我应该加上这一点。编辑中。 - Andy

Answer 1

可以使用动态规划算法实现。

为文本中的每个单词分配一个得分，该得分是以该单词开头时（即如果删除它前面的所有内容），以'r'结尾的最大行数。例如，最后一个单词的分数为0或1（取决于它是否以'r'结尾）。第一个单词的得分就是您需要的答案。

通过从后往前遍历单词来计算得分。对于给定的单词，分析创建第一行的所有可能性。对于给定的可能性，得分将是第二行中第一个单词的得分加1（如果第一行以“r”结尾）。给定单词的得分将是最佳可能性的得分。

使用示例文本“ The man was in the backgarden or the yard”：

yard: score 0
the: score 0
or: score 0 (only possibility for first line is "or the yard")
backgarden: score 1 (there are two possibilities for first line, the better one
                     is "backgarden or" which gives the score of "the" plus 1).
the: score 0 (only possibility for first line is "the backgarden")
in: score 1 (first line is "in the" which gives the score of "backgarden")
was: score 1
man: score 1 (first line is either "man was in" or "man was in the". The second
              option gives the score of "backgarden" which is 1.
The: score 1 (best first line is "The man was" which gives the score of "in").

在计算完分数后，要构建最佳的行分隔文本，您从第一个单词开始，选择第一行的最佳可能性（如上所述），然后重复下一行的第一个单词。

- interjay

---

我认为这个算法更适合使用深度优先搜索（dfs）而不是动态规划（dp）。 - smac89

@Smac89，我不明白你的评论。该算法是dp而不是dfs。 - interjay

不，我的意思是针对这个问题。解决它所需的算法应该是某种深度优先搜索，而不是动态规划。 - smac89

@Smac89 好的，我提供了一个解决方案的 dp 算法，所以我仍然不理解你的评论，除非你能展示一种在某些方面更好的 dfs 算法（我怀疑这点，因为假设最大行大小是常数，这个算法可以在线性时间内工作）。 - interjay

@Smac89 也许你所说的DFS是指直接递归搜索所有可能性，这将导致指数级时间复杂度。如果基于起始单词添加记忆化，则它基本上与我的算法相同，只不过是自顶向下的动态规划而不是自底向上的动态规划。 - interjay