计算将字符串分成至少 1 个元音的 3 个部分的可能性数量

Question

关闭。这个问题需要多问 focused 。目前不接受答案。

---

想要改进此问题吗？更新问题，使其仅关注一个问题 editing this post .

已关闭 8 年前。

Improve this question

我在动态规划中遇到了不同版本的“拆分成单词”或“单词分解”问题。我知道“断字”，但无法将其适应以下问题:

您将获得文件中的一段文本(最多 200 个字符)，并需要将该单词拆分为 3 个部分，每个部分至少包含 1 个元音。

例如，对于以下文本:bcaeiouxtz，我们可以有 6 种可能性:

bca eio uxtz
bca ei ouxtz
bca e iouxtz
bcae io uxtz
BCAE 我 ouxtz
bcaei 或 uxtz

我想编写动态编程方法，在其中我将能够计算我可以有多少种可能性。

如有任何帮助，我们将不胜感激，谢谢

Answer 1

不需要动态规划。一旦找到元音，第一个单词中的第一个是必需的，第三个单词中的最后一个是必需的。所以你只需要枚举之间的因素，aeiou -> eio，所以在中间你可以有e，ei 、eio、i、io、o。两个循环就足够了。