動的

Question

プログラミングとパスルーティング接近する方法がN×N個のサイズのアレイAから始まる乱数（-100 < = X < = 100）

が充填されている[0] [0]、 それに移動します隣接するインデックスをステージごとに表示します。

---

制限。

訪問先のインデックスに移動できません。

逆さまにすることはできません。

---

A [N-1] [N-1]への移動が終了すると、最大値を取得する必要があります。私が訪問した指標の

値は合計に追加されなければならない

この問題にアプローチする方法は何ですか？

---

[編集]

問題のよりコンパクトなステートメント：正方形N * Nの行列が与えられ、隣接するノード（NO対角線）を通過する任意の探索経路に沿って訪問先要素の最大和を見つけます[0]から出発して[0]と[N-1]で終わる[N-1]の制限内：

• 行を変更する際に、行インデックスは常に行に
• 一方を増加させる、COLインデックスは常に減少または増加する（すなわち、pa目はあなただけの列jで行iを離れる前に、最大合計を追跡し、2D状態D[i][j]を、必要

Answer 1

）すでに訪問したノード上の後戻りしません。最初の行は簡単に塗りつぶすことができます。これは単に行列の最初の行の接頭辞の和です。

次のすべての行について、次の考え方を使用できます。前の行を任意の列に残している可能性があります。前の行の終了列と現在の行の終了列（計算したい状態で定義）を知っている場合、その合計は前の行の終了列の累積値と2つの出口列の間の現在の行この合計は、全ての可能kため増分を計算することができること

D[i][j] = max_k (D[i - 1][k] + Sum{m from j to k} A[i][m]) 

注：と前の行のすべての可能な出口の列から、最大の和をもたらすいずれかを選択。 Sum{m from j to k}という表記は、jよりも小さいkに対しても有効である必要があります。これは、行を後方に移動することを意味します。

D[N-1][N-1]になるまで、これらの状態を行ごとに計算します。問題の解決策が得られます。