64. 最小路径和

题目

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例 1:

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2:

输入：grid = [[1,2,3],[4,5,6]]
输出：12

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100

首次AC

idea：记录到达每一个方格的 sum, 到达右下角时拿到最小最后两步中最小的 sum

func minPathSum(grid [][]int) int {
	rowLen := len(grid)
	columnLen := len(grid[0])
	step := rowLen - 1 + columnLen

	// 第 n 步 所在方格的 sum
	// sub[step]
	// []{ row:column:sum	}
	// 同一步数时，如果行数相同，那么就是同一个格子
	sumDic := make([]map[int]map[int]int, step)
	// 初始化第一步 (0,0)
	sumDic[0] = map[int]map[int]int{
		0: {
			0: grid[0][0],
		},
	}

	for i := 0; i < step; i++ {
		for r, dic := range sumDic[i] {
			for c, sum := range dic {
				right, down := nextStep([]int{r, c}, rowLen, columnLen)
				if right != nil {
					checkSum(i+1, sum, right, grid, sumDic)
				}
				if down != nil {
					checkSum(i+1, sum, down, grid, sumDic)
				}
			}
		}
	}
	return sumDic[step - 1][rowLen - 1][columnLen -1]
}

找到下一步的坐标

func nextStep(location []int, rowLen, columnLen int) (right, down []int) {
	down = nil
	if location[0] < rowLen-1 {
		down = []int{location[0] + 1, location[1]}
	}
	right = nil
	if location[1] < columnLen-1 {
		right = []int{location[0], location[1] + 1}
	}
	return
}

判断这个点的 sum 是否计算过，若果此次 sum 比之前小就替换掉节点的 sum 即只记录 minSum

func checkSum(step, nowSum int, location []int, grid [][]int, sumDic []map[int]map[int]int) {
	lastSum := sumDic[step][location[0]][location[1]]
	sum := nowSum + grid[location[0]][location[1]]
	// 如果走过了该节点且节点上次的点数小于这次的点数就不改变
	if lastSum > 0 && sum > lastSum {
		return
	}
	// 如果这次走到节点的点数更小就更新 minSum
	if sumDic[step] != nil {
		if sumDic[step][location[0]] != nil {
			sumDic[step][location[0]][location[1]] = sum
		} else {
			sumDic[step][location[0]] = map[int]int{
				location[1]: sum,
			}
		}
	} else {
		sumDic[step] = map[int]map[int]int{
			location[0]: {
				location[1]: sum,
			},
		}
	}
}