我在动态规划中遇到了不同版本的“拆分成单词”或“单词分解”问题。我知道“断字”，但无法将其适应以下问题:
您将获得文件中的一段文本(最多 200 个字符)，并需要将该单词拆分为 3 个部分，每个部分至少包含 1 个元音。
例如，对于以下文本:bcaeiouxtz，我们可以有 6 种可能性:
bca eio uxtz
bca ei ouxtz
bca e iouxtz
bcae io uxtz
BCAE 我 ouxtz
bcaei 或 uxtz
我想编写动态编程方法，在其中我将能够计算我可以有多少种可能性。
如有任何帮助，我们将不胜感激，谢谢
最佳答案
不需要动态规划。一旦找到元音，第一个单词中的第一个是必需的，第三个单词中的最后一个是必需的。所以你只需要枚举之间的因素，aeiou -> eio，所以在中间你可以有e，ei 、eio、i、io、o。两个循环就足够了。
关于计算将字符串分成至少 1 个元音的 3 个部分的可能性数量，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26967677/