ダンジョンゲームソリューションの説明

Question

ダンジョンゲームとして記述されています。 T 彼のダンジョンは、2DグリッドにレイアウトされたM×Nの部屋で構成されています。 私たちの勇敢な騎士（K）は、当初は左上の部屋 に位置し、王女を救うためにダンジョンを通って戦う必要がありました。

ナイトの初期ヘルスポイントは正の整数で表されます。 ヘルスポイントが0以下になると、すぐに死ぬ。

部屋の中には悪魔によって守られているものもありますので、騎士はこれらの部屋に入ると健康（負の整数）を失います。 他の部屋は空（0）か騎士の健康状態を増やす魔法の玉（正の整数）を含んでいます。

できるだけ早く王女に届くように、 騎士は各ステップで右または下にのみ移動することを決めます。

騎士の最小初期状態を決定する機能を書く。 プリンセスを救助できるようにする。

たとえば、以下のダンジョンを仮定すると、最初の健康状態は です.RIGHT-> RIGHT-> DOWN-> DOWNの最適なパスをたどった場合、ナイトは少なくとも7でなければなりません。

注：

騎士の健康状態には上限がありません。 部屋には、騎士が と入力した最初の部屋と、プリンセスが投獄されている右下の部屋であっても、脅威やパワーアップが含まれることがあります。

例：

dungeon = [[-2, -3, 4], 
      [-6, -15, 0], 
      [10, 25, -6]] 

回答：8

コードソリューションは、次のとおりです。

def dungeonGame(dungeon): 
    dp = [float("inf") for _ in dungeon[0]] 
    dp[-1] = 1 

    for i in reversed(range(len(dungeon))): 
     dp[-1] = max(dp[-1] - dungeon[i][-1], 1) 
     for j in reversed(range(len(dungeon[i]) - 1)): 
      min_HP_on_exit = min(dp[j], dp[j + 1]) 
      dp[j] = max(min_HP_on_exit - dungeon[i][j], 1) 

    return dp[0] 

誰かが上記の解決策が機能しているか説明できますか？提供されているサンプルを使ってdpのみをlen 3にするのはなぜですか？開始と終了の部屋を除いて、3つのステップしか必要ないので、それはありますか？なぜ隣接するdpの最小値を得てから最大値を得るのですか？また、最後の列が考慮されていないように見えるのは、jが1になるダンジョン[i] [j]（与えられた行列の例）です。私は解決策がうまく書かれていることを知っています。すべての道をどのように考慮しているかを理解しようとしています。

Answer 1

このアルゴリズムは、左下から右に向かって戻り、途中の各ステップで最適なスコアを見つけます。アルゴリズムをペンとペーパーで実行し、i、j、dpの現在の値を途中で書き留めておくことをお勧めします。それは本当に物事をクリアする必要があります。

（スタート）：いいえ、私とはまだありませんJ、DP = [INF INF 1]

あなたが勝つために右下に到達した後、少なくとも1 HPが必要になります。

（最初のループに入った後）：i = 2、dp = [inf inf 7]。

右下の四角自体の-6を生き残るには、7つの健康状態が必要です。

（内側のループに入った後）：

あなたは下の中央広場にいる場合は、最低限1衛生I = 2、J = 1、DP = [1 7 INF]をその広場の+25を生き延び、少なくとも7を必要とする隣の広場に到達するのに十分です。

これは、（中間結果の次の要素に格納されたdp[j + 1]）またはdp[j]の下位の間を選択する重要な行です。

min_HP_on_exit = min(dp[j], dp[j + 1]) 

移動ルール（のみダウン右に動かす）と3の対角線とダンジョンで、あなたはどんな後かもしれないだけで、ほとんどの3ヶ所があるので、中間結果への唯一の三つの要素があります。動きの数。

dp[-1] = max(dp[-1] - dungeon[i][-1], 1) 

理由：

ソルバがライン上に移動するたびに、最後の列は、ここでは特殊なケースとしての世話をされますか？まあ、それはあなたが右に動かすことができないという点で、他の列とは異なります。