ある日の大きなリート（最小経路和） 難易度：中 - Day20200723

問題

非負の整数を含むm×nの格子が与えられたとき、左上隅から右下隅まで、その経路上の数の和を最小にする経路を求めなさい。

説明

一度に下か右に一歩しか移動できません。

例

csharp
 :
[
 [1,3,1],
 [1,5,1],
 [4,2,1]
]
 : 7
 : 1→3→1→1→1→1の経路の和は最小だからである。

レンガを投げて玉を引き寄せる

すでにブラッシュアップされた類似のトピック：

• 異なる道 II
• ダンジョンゲームII

回帰の論理的な答えは、動的計画法、再帰の2つの方法で解決されます。

ダイナミックプログラミング

推論

• 各セルへの最小経路を記録
• をdp[m][n]に記録することが望ましい結果です。
• 各セルに到達する経路と可能性は次の2つです。
  • 一番上のセルから入る場合： dp[i][j] = dp[i][j-1]+grid[i][j].
  • 一番上のセルから入る場合： dp[i][j] = dp[i-1][j]+grid[i][j].
• インデックスに-1があるのは境界の問題です：
  • gridが0 longの場合、0を返します。
  • dp[0][0] = grid[0][0].
  • i=1,j=1で反復開始
  • dp[i][0],dp[0][j]は、デフォルト値として現在の行または列の累積を使用します。

javascript
/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function (grid) {
 let m = grid.length,
 n = grid[0] ? grid[0].length : 0
 if (m === 0 || n === 0) return 0
 let dp = Array.from({ length: m }, () => new Array(n).fill(Number.MAX_VALUE))

 //  
 dp[0][0] = grid[0][0]

 // パスの最初の行を完成させ
 for (let i = 1; i < m; i++) {
 dp[i][0] = dp[i - 1][0] + grid[i][0]
 }

 // パス合計の最初の列を完成させる
 for (let j = 1; j < n; j++) {
 dp[0][j] = dp[0][j - 1] + grid[0][j]
 }

 for (let i = 1; i < m; i++) {
 for (let j = 1; j < n; j++) {
 // 小道からのアクセス
 let itemMin = Math.min(dp[i - 1][j], dp[i][j - 1])
 dp[i][j] = Math.min(itemMin + grid[i][j], dp[i][j])
 }
 }
 return dp[m - 1][n - 1]
}

ディメンショナリティ

• dp降順は、各セルへの最小パスを記録しません。
• dp 各行への最小パスを記録

• 行パスの配置 髪オーdp[0]
• dp[j]に配置された列パス

javascript
/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function (grid) {
 let m = grid.length,
 n = grid[0] ? grid[0].length : 0
 if (m === 0 || n === 0) return 0

 let dp = new Array(n).fill(0)

 dp[0] = grid[0][0]

 // パス合計の最初の列を完成させる
 for (let i = 1; i < n; i++) {
 dp[i] = dp[i - 1] + grid[0][i]
 }

 for (let i = 1; i < m; i++) {
 // 各列のループの制限時間を開始するために、この列の始点のパス合計と、この列に到達する前のパスのパス合計を初期化する。
 dp[0] = dp[0] + grid[i][0]
 for (let j = 1; j < n; j++) {
 dp[j] = Math.min(dp[j - 1], dp[j]) + grid[i][j]
 }
 }
 return dp[n - 1]
}

再帰的

• パスを計算するロジックは上と同じで、エントリー＋現在のセルの値。
• 再帰的パラメータ、ランク、カラム
• 再帰的境界条件：
  • iとjの任意のポインタが境界を横切ると、ポインタと値を破棄するセルを指すために、最小を取るの最大値の使用は、それ自体が破棄されることを示します。
  • dpは、このセルを通るパスを格納し、直接dpに格納されている値を返します。

javascript
/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function (grid) {
 let m = grid.length,
 n = grid[0] ? grid[0].length : 0
 if (m === 0 || n === 0) return 0

 let dp = Array.from({ length: m }, () => Array(n).fill(0))

 //  
 dp[0][0] = grid[0][0]

 function get_sum(i, j) {
 if (i < 0 || j < 0) return Number.MAX_VALUE
 if (dp[i][j]) return dp[i][j]
 let itemMin = grid[i][j] + Math.min(get_sum(i - 1, j), get_sum(i, j - 1))
 dp[i][j] = itemMin
 return itemMin
 }

 return get_sum(m - 1, n - 1)
}

1つのユースケースが通過しなかったことがわかります。また、保存されたdpの次元削減のアイデアを利用することができます。

javascript
/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function (grid) {
 let m = grid.length,
 n = grid[0] ? grid[0].length : 0
 if (m === 0 || n === 0) return 0

 let dp = new Map()

 //  
 dp.set('0-0', grid[0][0])

 function get_sum(i, j) {
 if (i < 0 || j < 0) return Number.MAX_VALUE
 if (dp.has(i + '-' + j)) return dp.get(i + '-' + j)
 let itemMin = grid[i][j] + Math.min(get_sum(i - 1, j), get_sum(i, j - 1))
 dp.set(i + '-' + j, itemMin)
 return itemMin
 }

 return get_sum(m - 1, n - 1)
}