動的計画の無条件創造条件

動的計画の無条件創造条件
1つの問題はダイナミックプランニングを使用する必要があり、いくつかの条件を満たす必要があります.これらの条件は以前の文章でも列挙されています.内
いくつかの条件は適切に縮小することができて、ある条件は絶対に満たす必要があって、それは後効性がなくて、通俗的に現在の状態の計算で、前の状態はすでに確定しています.
ある时、一つの问题をダイナミックに计画する必要があることを知っているのに、どうしてどこか问题が発生したようなのか、落ち着いて考えてみると、どの条件が少し満たされていないのか.満たされなければどうするか、それは戦略を変えてアルゴリズムにこの条件を満たすことです.
次のテーマを見てください.テーマはleetcode 174に由来しています.
一部の悪魔は王女(P)を捕まえて地下城の右下に閉じ込めた.地下城はM x Nの部屋からなる二次元メッシュです.私たちの勇敢な騎士(K)は最初に左上の部屋に安置され、地下城を通り抜け、悪魔に対抗することで王女を救わなければならなかった.騎士の初期健康点数は正の整数です.もし彼の健康点数がある時0以下に下がったら、彼はすぐに死亡します.
一部の部屋は悪魔が守っているので、騎士はこれらの部屋に入ると健康点数を失う(部屋の値が負の整数であれば、騎士は健康点数を失う).他の部屋は空いている(部屋の値は0)か、騎士の健康点数を増やす魔法球が含まれている(部屋の値が正の整数であれば、騎士が健康点数を増やすことを示す).できるだけ早く王女に着くために、騎士は毎回右か下に1歩だけ移動することにした.騎士が王女を救うために必要な最低初期健康点数を計算する関数を作成します.
例えば、次のような配置の地下城を考慮すると、騎士が最適な経路に従って右->右->下->下であれば、騎士の初期健康点数は少なくとも7である.-2(K)   -3   3 -5    -10   1 10    30   -5(P )
説明:騎士の健康点数に上限はありません.どの部屋も騎士の健康点数に脅威を与える可能性があり、騎士が入った左上の部屋や王女が監禁されている右下の部屋を含む騎士の健康点数を増やす可能性があります.
このグリッドが見え、下に行くか右に行くしかなく、この問題は必ず動的に計画されていることがわかります.この問題は比較的基礎的な動的計画問題である.しかし、むやみにやると問題が発生しやすく、従来はこのような問題はすべて経路全体であり、最終的に目的地に着く代価を求めていた.この問題は、正負の代価の相殺が現れる.後の収益は前のパスの代価を相殺することはできません.通俗的に言えば、何も死なないことだ.もう死んでしまったので、後ろが血でも食べられない.例を挙げると、5->-7->10であり、この場合、経路全体の収益は正であるにもかかわらず、-7で処刑された場合、10はまったく意味がない.もし私たちが現在の残りの血量が最も多いことを確保する必要があるならば、しかし路地に入る可能性があり、後ろのすべての経路は血をたくさん消費します.もし私たちが後で消費する血量が少ないことを確保すれば、現在の残りの血量も見なければなりません.前後の状態が交錯すると,動的計画の要素を満たさない.しかし、この問題は、そんなによく知っているようで、直感的に自分に教えて、きっと動的な計画です.この時は問題を転換し、条件を創造しなければならない.正常なアルゴリズム人は必ずこの直感を持っていなければならない.転換に成功できるかどうかは能力次第だ.5->-7->10->-11->2->-4->20という経路があると仮定します.では、少なくともどれだけの血を持っていく必要があるのか、明らかに答えは最後の20とは関係ないに違いない.最後から2番目の数は-4であり、それは明らかに-4を通過する前に、少なくとも5滴の血がある.前へ、順番に類推する.後ろから前へ進む過程で、過去の状態が徹底的に確定していることがわかります.これは動的計画の要素を満たしている.この問題の転換戦略は,問題を逆に考慮し,後から前へ,各ステップの状態が決定されることにある.この時は2次元のメッシュに戻ります.  定義dp[i][j]は、(i,j)を通過する位置が終点に到達した場合に、その位置までに少なくとも必要な血量であり、S[i][j]は通過位置(i,j)で得られる血量であり、正の値は得られることを示す.dp[i][j+1]とdp[i+1][j]からdp[i][j]を特定できる.dp[i][j]=min(dp[i][j+1],dp[i+1][j])+S[i][j]滴血.これを負の値と算出すれば、少なくとも許容される血量は負の値ではなく、死ぬこともできないので、この位置までは少なくとも一滴の血が必要です.すなわち,最終結果と1に対してmaxをとる.この問題の肝心な転換は,左上から右下へ行くと,前の状態が確定せず,後効性がないことを満たすことである.変換問題は終点遡及源となり,この時点ですでに通り過ぎた状態が確定し,この考えが分かればコードが書きやすくなる.

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        dungeon[-1][-1] = max(1, 1- dungeon[-1][-1])
        #                  
        for j in range(len(dungeon[0])-1, 0, -1):
            dungeon[-1][j-1] = max(1, dungeon[-1][j] - dungeon[-1][j-1])
            #          ，           ，               。
        for i in range(len(dungeon)-1, 0, -1):
            dungeon[i-1][-1] = max(1, dungeon[i][-1] - dungeon[i-1][-1])
            #                
            for j in range(len(dungeon[0]) - 1, 0, -1):
                dungeon[i-1][j - 1] = max(1, min(dungeon[i-1][j], dungeon[i][j-1]) - dungeon[i-1][j - 1])
                # dp     
        return dungeon[0][0]

上のコードは元のマトリクス上で直接操作され,空間が開かれていない.空間を開く場合は、境界状況を単独で処理する必要がないように、1行1列多く開くことをお勧めします.本文を読んだ後、自分の思考と結びつけて、この問題だけではなく、一つの問題を把握してほしい.