最小路径和&不同路径——DFS记忆化搜索&动态规划

这两道题虽然粗看感觉挺简单的，但是需要考虑到的东西比较多，比如如果用dfs，需要通过记忆之前计算的答案进行剪枝，否则时间复杂度是指数级别，会导致超时，用动态规划的话反而简单许多。

# 最小路径和

dfs做法如下

```go
func minPathSum(grid [][]int) int {
    n := len(grid)
    m := len(grid[0])
    memo := make([][]int, n)
    for i := range memo {
        memo[i] = make([]int, m)
        for j := range memo[i] {
            memo[i][j] = -1
        }
    }
    res := dfs(grid, 0, 0, n, m, memo)
    return res
}

func dfs(grid [][]int, i, j, n, m int, memo [][]int) int {
    if i >= n || j >= m {
	// 极大值
        return 1 << 30
    }
    if i == n-1 && j == m-1 {
        return grid[i][j]
    }
    if memo[i][j] != -1 {
        return memo[i][j]
    }
    down := dfs(grid, i+1, j, n, m, memo)
    right := dfs(grid, i, j+1, n, m, memo)
    memo[i][j] = grid[i][j] + min(down, right)
    return memo[i][j]
}
```

动态规划

```go
func minPathSum(grid [][]int) int {
    n := len(grid)
    m := len(grid[0])
    dp := make([][]int, n)
    for i := range dp {
        dp[i] = make([]int, m)
    }
    dp[0][0] = grid[0][0]
    for i := 1; i < n; i++ {
        dp[i][0] = dp[i-1][0] + grid[i][0]
    }
    for j := 1; j < m; j++ {
        dp[0][j] = dp[0][j-1] + grid[0][j]
    }
    for i := 1; i < n; i++ {
        for j := 1; j < m; j++ {
            dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
        }
    }
    return dp[n-1][m-1]
}

```

# 不同路径

记忆化搜索

```go
func uniquePaths(m int, n int) int {
    memo := make([][]int, m)
    for i := range memo {
        memo[i] = make([]int, n)
        for j := range memo[i] {
            memo[i][j] = -1
        }
    }
    return dfs(0, 0, m, n, memo)
}

func dfs(i, j, m, n int, memo [][]int) int {
    if i >= m || j >= n {
        return 0
    }
    if i == m-1 && j == n-1 {
        return 1
    }
    if memo[i][j] != -1 {
        return memo[i][j]
    }
    down := dfs(i+1, j, m, n, memo)
    right := dfs(i, j+1, m, n, memo)
    memo[i][j] = down + right
    return memo[i][j]
}
```

动态规划

```go
func uniquePaths(m int, n int) int {
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
    }
    for i := 0; i < m; i++ {
        dp[i][0] = 1
    }
    for j := 0; j < n; j++ {
        dp[0][j] = 1
    }
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
        }
    }
    return dp[m-1][n-1]
}
```

Last modification：July 8, 2025