インタビューフォーラムで出会った質問は次のとおりです。
0と1で満たされた配列があります。0は溶岩の燃焼を表し、1は飛び石を表します。配列の最初から始めて、最後に到達するための最速の方法を見つけたいと考えています。各タイムステップで、速度Vを1ずつ増減するか、Vステップ離れた飛び石にジャンプすることができます。オーバーシュートせずに配列の最後に到達したい。
これを解決するための良いアルゴリズムは何ですか？
私はいくつかのことを試しましたが（主に動的計画法と再帰を使用して）、非指数関数的アルゴリズムにつながる最適な部分構造を見つけることができませんでした。何か案は？
各ステップでは、速度を上げるか、速度を上げないかの2つの選択肢があります。次に、これらのオプションごとに、異なるステップに進み、選択が繰り返されます。たぶん、ここに現れる木のパターンを見ることができます。ツリーの各ノードはステップであり、各エッジは選択肢です。各ノード（ステップ）には2つのエッジ（選択肢）があるため、二分木です。
また、速度Vのステップxにいる場合、どのようにそこに到達したかは関係ありません。次の結果は同じになります。したがって、ここで少し最適化できます。（たとえば、動的計画法を使用します。）
力ずくのアプローチは、このツリーを想像して、最終ステップに正確に到達するまで深さ優先探索を実行することです。複数の解決策があるかもしれません、そして最も速いものは解決策です。
ここでは動的計画法が正しいアプローチです。
探索空間は 2 次元です。現在の位置が最初の次元で、現在の速度が 2 番目の次元です。これは、2D 配列が必要であることを意味しますbest[N][N]。ここNで、 はブール配列内のアイテムの数です。の値は、 の速度で のbest[s,v]位置に到達するのに必要な最小ステップ数を表します。探索空間の各点を調べて、現在の速度で飛び石に到達できるかどうかを確認します。答えが「はい」の場合、検索スペースに対応するスポットを設定します。隣接する速度のポイントも設定します。答えは の位置にあります。svbest[N-1][0]