1行に2 * N個のピンがあり、N個は入力ピン、Nは出力ピンです。最小長ルーティングパス - 動的プログラミング
接続線は垂直方向にのみ行われ、水平に上半平面内と接続線はできることができる：このイメージのようにすべての入力端子には、単一の出力ピン及びその逆に接続する必要があります重複しない。
問題は、すべてのピンを接続するときに達成できるすべてのラインの最小長さです。上記の例で
、長さが31
括弧の問題は最適解ではないマッチングと同様スタックを使用して貪欲なアプローチです。
1と8の間の最も外側の線を見ると、ピンを2つのグループに分割します。 2〜7のうちの1つ、および9と10の間のものである。
これらのグループのそれぞれは、外行を超えて拡張することなく持つことができる最大行の高さに制約があります。 2つ目は最初のもの、もう1つは5つ目の2つ目のデフォルトです。
これはh <= maxHeightとpin[i]はleftPin+1とrightPinとpin[leftPin]の反対の型の間になるように高さhピンiを見つけることによって、その値を取得することができる機能lineLength(leftPin, rightPin, maxHeight)を与えます。
、行の長さがrightPin-leftPin+2*h + lineLength(leftPin+1, i-1, h-1) + lineLength(i+1, rightPin-1, 5)
あり、この機能のためにO(n^3)可能な値であるとメモ化して、それぞれの値を計算するであろう、なぜならhとiの繰り返しO(n^2)時間を必要とするであろう。したがって、合計時間はO(n^5)です。
これを改善するには、最大高さのバイナリ検索が必要です。
分裂と征服では、これをn^2に減らすことができます。
一般に、最初のピンは何かとペアにする必要があります。そのペアリングの唯一のオプションは、ピンのストリングが偶数の入出力ビットを持つ場合です。したがって、例＃1は＃8または＃10とペアにすることができます。
これらのペアごとに、ワイヤ内のサブ問題とワイヤ外のサブ問題にそのワイヤのコストを追加します。例えば
：我々は1と8をペアリングしている場合、その後、
cost = recursiveCost (2,7) + recursivecost(9,end) + wireCost(1,8)
あなたがそれをする必要がありますので、あなたは、内部関数呼び出しの最大再帰深度を追跡するためにも必要がありますwireCost（a、b）を計算します。
再帰の高さをどのように追跡しますか？ OPの例（接続がいずれかの方向に進むことができると仮定）では、6を3に接続すると、以前の関数呼び出しの高さが異なることを意味します。 –
再帰的メソッドは、構造体やクラスなどのラッパーオブジェクトで深度とコストを返すことができるため、呼び出し元がコストを計算して深さに追加することもできます。 – Chris
宿題？面接の質問？ –
入力ピンと出力ピンは固定されていますか？そうでなければ、答えは「3 * N」になるでしょう。 – user1952500
ピンは固定された位置にあります。 – user496940