サブシーケンス部分からのシーケンス？

Question

レッツは、私は以下の項目を持っていると言う：

1;2;3;4;5;[1,2];[3,4];[1,2,3];[2,3,4] 

（注：私はすべての順列が利用できていない、それらのほんの一部）

また、すべてのアイテムは、それに関連付けられたスコアを持っています。 は今、タスクが可能な部品のうち、シーケンスを構築することです：

1,2,3,4,5 

シーケンスを作成するには多くの方法があります。

the simplest : 1,2,3,4,5 
or : [1,2],[3,4], 5 
or : 1,[2,3,4], 5 
or : [1,2],[3,4],5 
or : ........ 

正しい順序はスコアが最も高いものでなければならないが。

どうすればよいですか？ グラフ？

Answer 1

再帰的なプロセスを使用してグラフを表示します。各サブシーケンスはノードです。エッジは、送信元ノードの終了整数が宛先ノードの第1の整数に隣接するノードを接続する。

たとえば、[1]から[2]、[2、3、4]までのエッジがあります。また、[1、2]から[3]と[3、4]までのエッジもあります。

これはダイクストラのアルゴリズムの問​​題を軽減し、重み付けされたエッジを持つグラフを通る最良の経路を見つけることになります。