2304. 网格中的最小路径代价

2304. 网格中的最小路径代价

• 难度: medium
• 原始链接: https://leetcode.cn/problems/minimum-path-cost-in-a-grid
• 标签: 动态规划

解法一: 递归

go

func minPathCost(grid [][]int, moveCost [][]int) int {
    m := len(grid)
    n := len(grid[0])
    ans := math.MaxInt
    visits := make([][]int, m)
    for i := 0; i < m; i++ {
        visits[i] = make([]int, n)
    }
    for i := 0; i < n; i++ {
        ans = min(ans, dfs(grid, moveCost, visits, 0, i, m, n))
    }
    return ans
}

func dfs(grid [][]int, moveCost [][]int, visits [][]int, i, j, m, n int) int {
    if visits[i][j] != 0 {
        return visits[i][j]
    }
    if i == m - 1 {
        return grid[i][j]
    }
    minVal := math.MaxInt
    for k := 0; k < n; k++ {
        minVal = min(minVal, dfs(grid, moveCost, visits, i + 1, k, m, n) + moveCost[grid[i][j]][k])
    }
    visits[i][j] = grid[i][j] + minVal
    return visits[i][j]
}

func min(num1, num2 int) int {
    if num1 <= num2 {
        return num1
    }
    return num2
}

解法二: 迭代

go

func minPathCost(grid [][]int, moveCost [][]int) int {
    m := len(grid)
    n := len(grid[0])
    arr := [][]int{
        make([]int, n),
        make([]int, n),
    }
    for i := 0; i < n; i++ {
        arr[0][i] = grid[0][i]
    }
    for i := 1; i < m; i++ {
        for j := 0; j < n; j++ {
            minVal := math.MaxInt
            for k := 0; k < n; k++ {
                minVal = min(minVal, arr[0][k] + moveCost[grid[i - 1][k]][j])
            }
            arr[1][j] = minVal + grid[i][j]
        }
        arr[0], arr[1] = arr[1], arr[0]
    }
    ans := math.MaxInt
    for _, num := range arr[0] {
        ans = min(ans, num)
    }
    return ans
}

func min(num1, num2 int) int {
    if num1 <= num2 {
        return num1
    }
    return num2
}