文章 224
评论 6
浏览 200759
Dynamic Programming - 64. Minimum Path Sum

Dynamic Programming - 64. Minimum Path Sum

64. Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example:

Input:
[
  [1,3,1],
[1,5,1],
[4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

思路:

题目意思是给一个网格,找出左上角到右下角最短路径和,和62、63、120题很像,都是经典dp最值问题,子问题就是走到当前位置从哪个方向过来的数值最小。

代码:

go:

// time: O(n^2), space: O(n^2)
/*func minPathSum(grid [][]int) int {

    if grid == nil {return 0}
    
    m := len(grid)
    n := len(grid[0])
    dp := make([][]int, m)
    for i := 0; i < m; i++ {
        dp[i] = make([]int, n)
    }
    
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if i == 0 && j != 0{
                dp[i][j] = dp[i][j-1] + grid[i][j]
            } else if  i != 0 && j == 0 {
                 dp[i][j] = dp[i-1][j] + grid[i][j]
            } else if i == 0 && j == 0 {
                 dp[i][j] = grid[i][j]
            } else {
                dp[i][j] = min(dp[i][j-1] + grid[i][j], dp[i-1][j] + grid[i][j])
            }
        }
    }
    
    return dp[m - 1][n - 1]
}*/

// time: O(n^2), space: O(1)
func minPathSum(grid [][]int) int {
    if grid == nil {return 0}
    
    m := len(grid)
    n := len(grid[0])

    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if i == 0 && j != 0{
                grid[i][j] += grid[i][j-1]
            } else if  i != 0 && j == 0 {
                grid[i][j] += grid[i-1][j]
            } else if i == 0 && j == 0 {
                grid[i][j] = grid[i][j]
            } else {
                grid[i][j] = min(grid[i][j-1] + grid[i][j], grid[i-1][j] + grid[i][j])
            }
        }
    }
    
    return grid[m - 1][n - 1]
}

func min (i, j int) int {
    if i < j {
        return i
    }
    return j
}```

标题:Dynamic Programming - 64. Minimum Path Sum
作者:michael
地址:https://www.bitbo-liuyang.com/articles/2019/08/05/1565019675636.html

Nothing just happens, it's all part of a plan.

取消