アルゴリズムの復習：最小経路和

前節では、動的計画問題」を分析し、解くことに成功しました。このセクションでは、この「パスの和」問題を完全に把握するために、似たようなタイプの問題を引き続き見ていきます。さっそく，問題を見てみましょう．

トピック分析

注意：一度に移動できるのは下か右の1ステップのみです。

例

 :
[
 [1,3,1],
 [1,5,1],
 [4,2,1]
]
 : 7
 : 経路1→3→1→1→1が最も和が小さいからだ。

この問題は少し難しいです！アイデアが浮かばない場合は、前回の勉強を見直してください！

問題解決策を直接見ることはお勧めしません！

トピックイラスト

まず最初に、私たちが探しているのは 最小経路和 です。m * n: [[1,3,1],[1,5,1],[4,2,1]] という長方形があるとします。

そうすると、左上隅から右下隅への最小パスの和は1-3-1-1-1であることが簡単にわかります。

トピックが明確であり、分析が続いています。問題は前回の三角形の最小経路和を求める問題と同じで、部分問題の最適解から組み立てられるということで、テーマは明らかに一致しているので、動的計画法を使って解くことを考えましょう。まず、状態を定義します：

繰り返しになりますが、右下隅へのパスはすべて要素[0,0]を通るからです。ですから、dp[0][0]を初期化する必要があります。

分析を続けると、問題で与えられた条件によれば、dp[i][j]が必要であれば、それは自分自身の上か左から移動したはずです。これを下図に示します：

5, 3または1からしか移動できない 2, 5または4からしか移動できない 4, 1から移動できる 3, 1から移動できる

これが状態遷移方程式につながります：

ここでも2つの特別なケースを考慮する必要があります：

• 最上段、左からのみ移動可能
• 一番左の列で、上からしか動かせません。

最後に、ゴールは左上隅から右下隅まで歩くことなので、グリッド全体の最小経路和は、実際には右下隅の要素を含む最小経路和です。つまり

これで、4つのステップで行われた分析は終了です：

1. 状態の定義
2. 状態遷移方程式の要約
3. 状態遷移方程式を満たすことができない特殊なケースを分析します。
4. 最終解答を入手

GO言語の例

以上の分析から、コードは以下のようになります：

func minPathSum(grid [][]int) int {
	l := len(grid)
	if l < 1 {
		return 0
	}
	dp := make([][]int, l)
	for i, arr := range grid {
		dp[i] = make([]int, len(arr))
	}
	dp[0][0] = grid[0][0]
	for i := 0; i < l; i++ {
		for j := 0; j < len(grid[i]); j++ {
			if i == 0 && j != 0 {
				dp[i][j] = dp[i][j-1] + grid[i][j]
			} else if j == 0 && i != 0 {
				dp[i][j] = dp[i-1][j] + grid[i][j]
			} else if i !=0 && j != 0 {
				dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
			}
		}
	}
	return dp[l-1][len(dp[l-1])-1]
}
func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

走行結果

上記のコードを実行すると、メモリを使いすぎていることがわかります。メモリを圧縮する方法はないでしょうか？観察したところ、左上から右下への各ノードの最小経路和を計算する過程で、累積的に計算され、再度アクセスする必要のない要素データのみを使用する必要があることがわかりました。グラフにすると以下のようになります：

最適化されたコードは以下の通り：

func minPathSum(grid [][]int) int {
	l := len(grid)
	if l < 1 {
		return 0
	}
	for i := 0; i < l; i++ {
		for j := 0; j < len(grid[i]); j++ {
			if i == 0 && j != 0 {
				grid[i][j] = grid[i][j-1] + grid[i][j]
			} else if j == 0 && i != 0 {
				grid[i][j] = grid[i-1][j] + grid[i][j]
			} else if i !=0 && j != 0 {
				grid[i][j] = min(grid[i-1][j], grid[i][j-1]) + grid[i][j]
			}
		}
	}
	return grid[l-1][len(grid[l-1])-1]
}
func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

走行結果

授業後の振り返り：パスとクラスの問題と、部分クラスの問題の違いは何ですか？

私が書いたすべての解答と各問題の完全な図解をeBookにまとめました。