golang刷leetcode动态规划（12）最小路径和

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

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

示例:

输入:

[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]

复制

输出: 7

解释: 因为路径 1→3→1→1→1 的总和最小。

解题思路

1,这也是一个典型的动态规划题

2，是递增的

3，状态转移方程为

if step[i-1][j]<step[i][j-1]{
   step[i][j]=step[i-1][j]+grid[i][j]
}else{
  step[i][j]=step[i][j-1]+grid[i][j]
}

复制

归纳总结

1，这种矩阵寻找路径类型的题目基本都是动态规划题目

2，动态规划问题都可以递归解，只不过利用空间换时间，存储了最优子结构

3，动态规划主要考察的是问题拆分能力，将一个问题拆分为一个个小问题，然后各个击破。

代码实现

func minPathSum(grid [][]int) int {
    if len(grid)==0{
        return 0
    }
    step:=make([][]int,len(grid))
    for i:=0;i<len(grid);i++{
        step[i]=make([]int,len(grid[0]))
    }
    
    step[0][0]=grid[0][0]
    for i:=1;i<len(grid);i++{
       step[i][0]=step[i-1][0]+grid[i][0]
    }
    for i:=1;i<len(grid[0]);i++{
        step[0][i]=step[0][i-1]+grid[0][i]
    }
    for i:=1;i<len(grid);i++{
        for j:=1;j<len(grid[0]);j++{
            if step[i-1][j]<step[i][j-1]{
                 step[i][j]=step[i-1][j]+grid[i][j]
            }else{
                step[i][j]=step[i][j-1]+grid[i][j]
            }
        }
    }
    return step[len(grid)-1][len(grid[0])-1]
}

复制