1
记录下自己的解题步骤，备忘。64题
题目： 给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
1
2
3
4
5
6
7
8
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
看到这个题时，因为是一个起点到终点的过程，并且从当前状态到下一状态有确定的转移方式，故想到可以使用dfs来解，又是一个最值问题，也可以用动态规划来解题。
我先使用了dfs来解题
1
2
3
4
5
思路：因为每次只能向下或者向右移动一步，设当前状态为(i, j)，下一个状态为右移动一步(i, j+1)或者往下移动一步（i+i, j），因为是求路径和，故需要递归时保存和，并且每次递归都需要加上当前节点值，即：
sum += grid[i][j]
对于每次的这两个变化，取最小值，不停递归，直到终点或超出边界返回。
下面是go代码（提交后超出时间限制）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
func minPathSum(grid [][]int) int {
if len(grid) == 0 {
return 0
}
return dfs(grid, 0, 0, 0, 1<<31 - 1)
}
//grid是当前二维数组，i，j是当前位置，sum为每进行一步的累加值，minSum为最小值（只有走到终点时才进行更新）
func dfs(grid [][]int, i int, j int, sum int, minSum int) int {
if i > len(grid) - 1 {
return minSum
}
if j > len(grid[0]) - 1 {
return minSum
}
sum += grid[i][j]
if i == len(grid) - 1 && j == len(grid[0]) - 1 {
if sum < minSum {
minSum = sum
}
return minSum
}
return min(dfs(grid, i+1, j, sum, minSum), dfs(grid, i, j+1, sum, minSum))
}
func min(m, n int) int {
if m < n {
return m
}
return n
}
起点移动到终点，距离为m+n，又因为每次移动有两个选择，故时间复杂度：
1
O(2^(m+n))
递归深度为m+n，故空间复杂度
1
O(m+n)
使用动态规划来处理：
1
2
3
4
5
6
7
8
对于一个点(i, j)来说，他是由这个点的左边：(i-1, j)或者上面(i, j-1)走过来的，
所以如果已知了(i-1, j)和(i, j-1)的最小路径值，那么对于(i, j)这个点来说，
它的最小路径值就是:min(路径值(i-1, j) + grid[i][j], 路径值(i, j-1) + grid[i][j])。
用dp的二维数组来表示最小路径和，则转移函数就是：
dp[i][j] = min(dp[i-1][j]+grid[i][j], dp[i][j-1]+grid[i][j])
初始值：dp[0][0] = grid[0][0]
第一行只能由其左边转移过来，故dp[0][i] = dp[0][i-1] + grid[0][i]
第一列只能由其上面转移过来，故dp[i][0] = dp[i-1][0] + grid[i][0]
下面是go代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
func minPathSum(grid [][]int) int {
m := len(grid)
if m == 0 {
return 0
}
n := len(grid[0])
dp := make([][]int, m)
for i := 0; i < len(grid); i++ {
dp[i] = make([]int, n)
}
dp[0][0] = grid[0][0]
for i := 1; i < n; i++ {
dp[0][i] = dp[0][i-1] + grid[0][i]
}
for i := 1; i < m; i++ {
dp[i][0] = dp[i-1][0] + grid[i][0]
}
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
dp[i][j] = min(dp[i-1][j]+grid[i][j], dp[i][j-1]+grid[i][j])
}
}
//fmt.Println(dp)
return dp[m-1][n-1]
}
func min(m, n int) int {
if m < n {
return m
}
return n
}
时间复杂度：
1
O(mn)
空间复杂度：
1
O(mn)
本题可以针对空间进行优化， 考虑到点(i, j)，其只用到左边和上边，故可优化为一维数组，数组长度为grid的m 当然还可以直接使用grid来记录最小路径和
