1. 序章

このチュートリアルでは、左側に表示されているブロックと右側に表示されているブロックを使用してブロックを配置する方法の数を計算する方法を説明します。

2. 問題の説明

高さがからまでの整数である一意のサイズのブロックがあります。ブロックを左から正確に表示し、ブロックを右から表示するようにブロックを行に配置する方法はいくつありますか。

左側にブロックがなくなった場合、ブロックは左側から表示されます。 同様に、ブロックの右側にブロックがなくなった場合、ブロックは右側から表示されます。

たとえば、でブロックを配置すると、高さ、、、のブロックが左から表示されます。 また、高さのあるブロックは右から見ることができます。

高さの最も長いブロックが両側から見えます。

3. 左の部分を解く

まず、左側の部分だけを考えてみましょう。 与えられたブロックを、左から見えるブロックでそれらを配置する方法の数を示しましょう。 この問題は2つのケースに分けることができます。

最初のケースでは、最後に最長のブロックを配置します。 このように、残りのブロックをどのように配置しても、最も長いブロックが常に左から見えるようになります。したがって、残りのブロックを表示可能なブロックに配置する方法の数を見つける必要があるため、問題は解決することになります：

2番目のケースでは、最長のブロック以外のブロックを最後に配置します。 最長のブロックは終了位置にないため、最後のブロックを含め、その直後のブロックを非表示にします。 したがって、最後のブロックを左から見えるブロックとして数えるべきではありません。 左から見えるブロックを作るには、残りのブロックに配置する必要があります。したがって、問題は、残りのブロックを見えるブロックに配置することを解決することになります：

短いブロックを最後の位置に配置する方法が考えられるため、2番目のケースの合計方法数はです。

上記の観察に基づいて、漸化式を得ることができます。

基本ケースの場合、ブロックが1つしかない場合、左から見えるようにする方法は1つだけです。 したがって、を持つことができます。 また、のために持っています。

動的計画法を使用してを計算できます。

このアルゴリズムは、2次元配列を使用してを計算します。 配列のインデックスは。から始まるため、配列には行と列があります。 この配列を使用して、計算値を格納します。 より大きなとで計算する場合、以前に計算された結果をより小さな数から再利用できます。

まず、ベースケースのを配列に格納します。 次に、ネストされたループを使用して、すべての可能な値と値を調べ、漸化式に基づいて計算します。 計算が終了したら、それが私たちが望む結果です。

数値とに2つのネストされたループがあるため、このアルゴリズムの全体的な時間計算量はです。

4。 両方のパーツをS0lve

左から見えるブロックと右から見えるブロックを含む配置を考えてみましょう。 表示されているブロックごとに、このブロックと、そのブロックと次の表示されているブロックの間のすべてのブロックをセグメント全体として扱います。 最長のブロックは、それ自体のみを含むセグメントです。 また、両側から見ることができます。 したがって、最長のブロックセグメントの前にセグメントがあり、最長のブロックセグメントの後にセグメントがあります：

右側のセグメントごとに、ブロックの順序を逆にして、セグメント全体を左側に移動できます。 これにより、最長のブロックの前にセグメントが作成されます。 また、これらのセグメントを各セグメントの最も高いブロックに基づいて並べ替えることができます。このようにして、最も長いブロックの左側にブロックを表示できます：

同様に、最長のブロックが最後の位置にあり、左から見えるブロックがあるブロック配置が与えられた場合、セグメントを選択して、最長のブロックの右側に移動できます。 このようにして、左から見えるブロックと右から見えるブロックを含むブロック配置を作成できます。

したがって、元の問題を、最も長いブロックが終了位置にあり、残りのブロックの間に表示可能なブロックがある配置を計算する小さな問題、つまりに減らすことができます。

また、セグメントの中から任意のセグメントを選択して右に移動することができます。 したがって、可能な方法の総数は、であり、これもです。

階乗関数と前の関数を使用して、結果を計算できます。

階乗関数の時間計算量はです。 また、機能に時間がかかります。 したがって、このアルゴリズムの全体的な時間計算量は次のようになります。

5. 結論

このチュートリアルでは、左からブロックが見えるブロックの配置数を計算する動的計画法アルゴリズムを示しました。 このアルゴリズムに基づいて、左から見えるブロックと右から見えるブロックを持つブロックの配置数を計算するように拡張できます。