動的プログラミング疑問

Question

問題Minimum number of jumps to reach endでは、重複するサブ問題はどこですか？

Answer 1

グラフを横断する方向を反転すると重なり合うサブ問題が発生し、すべての可能なケースを解決する計算量が大幅に減ります。

単純な解決策では、要素が選択されるたびに、配列の終わりに達するまで、可能なパスを反復処理する必要があります。

しかし、ダイナミックプログラミングのアプローチでは、私たちがしようとしているのは私たちの目標から後ろ向きに作業することです。そこに到達するための最短経路を見つけるのではなく、基礎となるサブ問題を使用します：私の現在のノードに到達するにはどのノードから来ていますか？そして最も重要なのは、このアプローチを適用する場合、は、重複計算なしですべての可能な項目の回答を提供します。

これはあなたに、各ノードのすべての答えを与える以下のアルゴリズムにつながる：現在のノードを取り、その可能性のすべてのノードを見つける配列

に

1. スタート最後の項目で1つのステップでそこから来た
2. 初めてこのノードに到達した場合は、そのノードと最後のノードの間の最短経路までの経路を保存してください。
3. ノード、結果を破棄する
ステップ2から
4. 繰り返し配列にノードを使用すると、あなたが今、アレイ