64. 最小路径和

[yankewei]

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

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

示例:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-path-sum

解答

这个题一看就是动态规划题，我的思路是，要想到达右下角，有两种方式。
第一种：到达右下角上边的元素
第二种：到达右下角左边的元素
然后对比这两种元素，哪个加起来最小，那就选择哪个，依次类推：
数组只剩下一行：到达最后的元素就是这一行数据相加即可
数组只剩下一列：到达最后的元素就是这一列数据相加即可

动态规划 + 递归

func minPathSum(grid [][]int) int {
    m := map[string]int{}
    return dp(grid, m)
}

func dp(grid [][]int, m map[string]int) int {
    rows, columns := len(grid), len(grid[0])
    str := strconv.Itoa(rows) + "*" + strconv.Itoa(columns)
    if v, e := m[str]; e {
	return v
    }
    if rows == 1 {
        var ret int
	for _, v := range grid[0] {
	    ret += v
	}
        return ret
    }

    if columns == 1 {
	var ret int
	for _, v := range grid {
	    ret += v[0]
	}
	return ret
    }

    top := grid[:rows-1]

    left := [][]int{}
    for i := 0; i < rows; i++ {
	left = append(left, grid[i][:columns-1])
    }

    mix := min(grid[rows-1][columns-1]+dp(top, m), grid[rows-1][columns-1]+dp(left, m))
    m[str] = mix
    return mix
}

func min(x, y int) int {
    if x > y {
	return y
    }
    return x
}

这个思路应该是最菜的思路了，有时间再来优化一下。