最小路径和

1. 题目描述

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

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

2. 思路

1. 思路一
   • DFS：每到达一个(i, j)就把该位置的数字加到sum中
   • 只能往右或者往下走，因此不会走重复(i,j)，故不需要set记录走过的(i,j)
2. 思路二
   • DFS+缓存
3. 思路三
   • 动态规划

3. 实现

3.1. DFS

func minPathSum(grid [][]int) int {
    minCount := math.MaxInt32
    minPathSumDFS(grid, 0, 0, len(grid), len(grid[0]), 0, &minCount)
    return minCount
}

func minPathSumDFS(grid [][]int, row, col, m, n, currentCount int, minCount * int) {
    if invalid(row, col, m, n) {
        return
    }

    currentCount += grid[row][col]

    if exceedEnd(row, col, m, n) {
        *minCount = min(*minCount, currentCount)
        return
    }


    minPathSumDFS(grid, row+1, col, m, n, currentCount, minCount)
    minPathSumDFS(grid, row, col+1, m, n, currentCount, minCount)
}

func invalid(row, col, m, n int) bool {
    if row < 0 || row >= m || col < 0 || col >= n {
        return true
    }

    return false
}

func exceedEnd(row, col, m, n int) bool {
    return row==m-1 && col == n-1
}

func min(a, b int) int {
    if a < b {
        return a
    }

    return b
}

3.2. DFS+缓存

func minPathSum(grid [][]int) int {
    memo := make(map[string]int, 0)
    return minPathSumDFS(grid, 0, 0, len(grid), len(grid[0]), memo)
}

func minPathSumDFS(grid [][]int, row, col, m, n int, memo map[string]int) int {
    count, ok := memo[getKey(row, col)]
    if ok {
        return count
    }

    if invalid(row, col, m, n) {
        return math.MaxInt32
    }

    if exceedEnd(row, col, m, n) {
        return grid[row][col]
    }



    minCount := math.MaxInt32
    minCount = min(minCount, minPathSumDFS(grid, row+1, col, m, n, memo))
    minCount = min(minCount, minPathSumDFS(grid, row, col+1, m, n, memo))

    if minCount == math.MaxInt32 {
        minCount = 0
    }

    memo[getKey(row, col)] = minCount + grid[row][col]
    return minCount + grid[row][col]
}

func invalid(row, col, m, n int) bool {
    if row < 0 || row >= m || col < 0 || col >= n {
        return true
    }

    return false
}

func getKey(row, col int) string {
    return fmt.Sprintf("%v:%v", row, col)
}


func exceedEnd(row, col, m, n int) bool {
    return row==m-1 && col == n-1
}

func min(a, b int) int {
    if a < b {
        return a
    }

    return b
}

3.3. 动态规划

func minPathSum2(grid [][]int) int {
	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[0]); j++ {
			if i == 0 && j == 0 {
				continue
			} else if i == 0 {
				grid[i][j] = grid[i][j-1] + grid[i][j]
			} else if j == 0 {
				grid[i][j] = grid[i-1][j] + grid[i][j]
			} else {
				grid[i][j] = min(grid[i-1][j], grid[i][j-1]) + grid[i][j]
			}

		}
	}
	return grid[len(grid)-1][len(grid[0])-1]
}

func min(a int, b int) int {
	if a < b {
		return a
	}

	return b
}

4. 参考

• 最小路径和 （动态规划，规范流程，清晰图解） - 最小路径和 - 力扣（LeetCode）