グラフ（発展）グラフDP

LeetCode 練習問題集

問題	難易度	重要度	テクニック
Longest Path With Different Adjacent Characters	★★★★	高	グラフDP
Second Minimum Time to Reach Destination	★★★★★	中	グラフDP
Shortest Path to Get All Keys	★★★★★	中	グラフDP
Clone Graph	★★★★	高	グラフDP
Cheapest Flights Within K Stops	★★★★	高	グラフDP
Last Day Where You Can Still Cross	★★★★★	高	グラフDP

グラフはさまざまな分野と組み合わせて問題を作ることができます。そのため実際には臨機応変に対応する必要があります。その中でも重要で幅広く応用が可能なものとしてグラフDPを紹介します。本章の例題では解説ではなくヒントをおいています。難しいと感じた時はヒントを元に考えてみましょう。詳細な解説はソースコードの部分に記載します。

グラフDP

実はグラフDP自体は二分木ですでに触れています。例えば二分木で登場した二分木（基礎）BFS, DFS - 例題2. Diameter（直径）はまさにグラフDP（木DP）を行なっています。一般的には各ノードが一つの状態を表し、そのノード（状態）における情報を元に隣接しているノード（遷移先の状態）の情報を求めていくイメージです。

通常のDP同様に貰うDP（ボトムアップ, take）と配るDP（トップダウン, give）のどちらを使うかを意識しながら練習してみましょう。どの問題も難易度は高いです。問題を解く前に二分木の木DPの問題及びDPを復習しておきましょう。