1. 概要

このチュートリアルでは、特定の配列の最初から最後に到達するためのジャンプの最小数を見つける問題について説明します。

まず、問題を定義し、それを説明するための例を示します。 次に、それを解決するための3つの異なるアプローチを提示し、それらの実装と空間および時間の複雑さを処理します。

2. 問題の定義

正の整数の配列があり、その配列の各要素は、右にジャンプできる最大の長さを表しているとします。 配列の終わりを最後の要素の後の位置と見なします。 最初の要素から配列の最後に到達するまでに実行できるジャンプの最小数を見つけるように求められました。

次の例を見てみましょう。

与えられた配列の最後に到達するには、さまざまな方法があります。 それらのいくつかを見てみましょう：

  • .
  • .
  • .

ご覧のとおり、指定された配列の最後に到達するためのジャンプの最小数は、です。ここで、パスを取得します。

3. 素朴なアプローチ

3.1. 本旨

このアプローチの主なアイデアは、考えられるすべての解決策を試し、最小のジャンプ数で最適な解決策を取得することです。

最初に、考えられるすべての解決策を試すための再帰的な方法があります。 現在の要素値以下の距離で、各位置からすべての生細胞にジャンプしようとします。 電話をかける（ジャンプ）たびに、ジャンプの数を1つ増やします。

最後に、可能なすべての呼び出しの間の最小値を取ります。これは、現在の要素から開始して、指定された配列の最後に到達するためのジャンプの最小数を表します。

3.2. アルゴリズム

アルゴリズムの実装を見てみましょう。

最初に、関数を宣言します。この関数は、指定された配列の最後に到達するために可能なすべてのソリューションを試行します。 関数には2つのパラメーターがあります。指定された配列と、配列内の現在の位置を表します。

まず、ここでの再帰関数の基本ケースは、配列の最後に到達したときです。次に、配列の最後から開始して、指定された配列の最後に到達するための最小ジャンプ数を返します。

次に、を宣言します。これは、現在の位置から開始して、指定された配列の最後に到達するためのジャンプの最小数を表します。 最初は、その値は無限大に等しくなります。 次に、可能なすべての動きの中で最小限の答えを取ります。 その位置に現在のジャンプを表す1を加えたものから始まる、可能な次の位置ごとに最適な答えが得られます。

最後に、は、最初の要素から開始して、指定された配列の最後に到達するための最小ジャンプ数を返します。

3.3. 複雑さ

最悪の場合の時間計算量はです。ここで、は指定された配列の長さであり、は配列内の最大値です。 配列内の位置ごとに、ジャンプの最大長を表す選択肢があります。

一方、このアルゴリズムのスペースの複雑さはです。 この複雑さの背後にある理由は、ジャンプの最小数に等しい単一の変数を使用するためです。

4. 動的計画法アプローチ

4.1. 本旨

このアプローチの主な考え方は、前の考え方と同じです。 ただし、状態が重複しているため、動的計画法を使用できます。

最初、この動的計画法アプローチの状態は、になります。これは、位置から開始して配列の最後に到達するためのジャンプの最小数を表します。 次に、各状態の答えは次の状態の答えに依存するので、最後から最初に向かって各状態の答えの計算を開始します。 次に、各状態について、範囲内のすべての状態の解の中で最小値を取ります。

最後に、は、最初の位置から開始して、指定された配列の最後に到達するためのジャンプの最小数を表します。

4.2. アルゴリズム

アルゴリズムの実装を見てみましょう。

最初は、前のアプローチと同じ機能があります。 指定された配列を表す1つのパラメーターがあります。

最初に、配列を宣言します。これは、各位置から開始して配列の最後に到達するための最小ジャンプ数を格納します。

次に、の値をに設定します。これは、最後から最後に到達するためのジャンプの最小数を表します。 次に、最後から最初までの各位置について、範囲内のすべてのセルの中で最小の答えを持つセルにジャンプしようとします。

最後に、は、最初の要素から開始して、指定された配列の最後に到達するための最小数のジャンプを持ちます。

4.3. 複雑

このアルゴリズムの時間計算量はです。ここで、は指定された配列の長さであり、はジャンプの最大長です。 この複雑さの背後にある理由は、各ポジションについて、可能な限りジャンプするように努めているためです。

このアルゴリズムのスペースの複雑さはです。ここで、は指定された配列の長さです。 その理由は、各位置のジャンプの最小数を保存するためです。

5. 欲張りアプローチ

5.1. 本旨

このアプローチの主なアイデアは、可能な限り前進し続けることです。 動けなくなった瞬間、通過したすべてのセルの中から可能な限り遠くまでジャンプします。

最初に、このアプローチでは、次の2つのことに注意します。

  1. 最大到達可能性：これは、繰り返したジャンプの1つを使用して到達できる最大位置を表します。
  2. 移動：最後に行ったジャンプを使用して実行できる移動の数。

次に、配列を反復処理しながら、到達できる最大位置を更新し、移動回数を1つ減らします。 動きがなくなった瞬間に、最大位置に到達できるセルからジャンプし、ジャンプの数を1つ増やします。

結局、ジャンプの数は私たちが作ることができる最適な解決策であり、それが問題の答えになるでしょう。

5.2. アルゴリズム

アルゴリズムの実装を見てみましょう。

最初は、以前のアプローチと同様の機能があります。

最初に、変数を宣言します。これは、通過したセルを使用して到達できる最大位置を格納します。 最初は、最初の要素と同じです。

また、最後のジャンプを使用して実行できる最大移動数を格納する変数を宣言します。 その初期値は、最初の要素にも等しくなります。 さらに、を宣言します。これは、これまでに行ったジャンプの数を格納し、最初は最初の要素からのジャンプを表す1に等しくなります。

次に、指定された配列の要素をループします。 各反復で、現在のジャンプの最大長を使用する次の位置で最大化します。 また、移動できる回数を1つ減らします。 その後、が不足していないか確認します。 もしそうなら、私たちはその位置に私たちを連れて行くセルを使ってジャンプします。

さらに、の新しい値はに等しくなります。これは、現在の位置から移動する必要がある位置に到達するための最良のジャンプを使用することを決定したためです。

最後に、は、最初の要素から開始して配列の最後に到達するために必要な最小数のジャンプを持ちます。

5.3. 複雑

このアルゴリズムの時間計算量はです。ここで、は指定された配列の長さです。 この複雑さは、各位置を1回だけ繰り返すためです。

このアルゴリズムのスペースの複雑さはです。 その理由は、変数の数が一定であるためです。

6. 結論

この記事では、配列の最後に到達するためのジャンプの最小数を見つける問題について説明しました。 まず、問題を説明する例を示しました。 次に、それを解決するための3つの異なるアプローチを検討しました。それぞれのアプローチは、前のアプローチよりも時間計算量が優れていました。

最後に、それらの実装をウォークスルーし、それぞれの背後にある考え方を説明しました。