<p>顺便说一句,你的问题是NP完全的(这意味着它没有“快速”的多项式时间解),它对于小问题是可以解决的,但是它很快就会变得非常困难。在</p>
<p>你的问题可以看作是<a href="https://en.wikipedia.org/wiki/Longest_path_problem" rel="nofollow noreferrer">longest-path problem on a directed graph</a>。在</p>
<ul>
<li>画一个<a href="https://en.wikipedia.org/wiki/Directed_graph" rel="nofollow noreferrer">directed graph</a>,每个单词(国家)表示为一个顶点。在</li>
<li>对于每对单词<code>w1</code>和<code>w2</code>,如果<code>w1</code>的最后一个字母与<code>w2</code>的第一个字母相同,则画一条边<code>w1 -> w2</code>。在</li>
<li>如果<code>w2->w1</code>的最后一个字母与<code>w1</code>的第一个字母相同,则从<code>w2->w1</code>绘制反向边缘。在</li>
<li>找到<a href="https://en.wikipedia.org/wiki/Longest_path_problem" rel="nofollow noreferrer">maximum-length path</a>-包含最多顶点的简单路径。(“简单”在本例中是指“不包含任何顶点多次。”)</li>
</ul>
<p>下面是一个水果和蔬菜列表的示例图:<code>Apple, banana, eggplant, kiwifruit, orange, oregano, tangerine, zucchini</code>。在</p>
<p><img src="https://i.stack.imgur.com/1oqFg.jpg" alt="Word DAG Example"/></p>
<p>此图可能包含循环(例如,此图有一个循环<code>eggplant -> tangerine -> eggplant -> tangerine....</code>。<a href="https://en.wikipedia.org/wiki/Longest_path_problem#Relation_to_the_shortest_path_problem" rel="nofollow noreferrer">The longest path problem for directed graphs containing cycles is NP-complete.</a>因此这个问题没有多项式时间解。在</p>
<p>这并不意味着你不能比暴力做得更好。<a href="https://stackoverflow.com/questions/2525316/longest-acyclic-path-in-a-directed-unweighted-graph">There's a dynamic programming algorithm</a>,它将复杂度从<code>O(n!)</code>(阶乘,<em>非常</em>bad)降低到{<cd12>}(超指数,仍然不好,但比阶乘好)</p>