AGV机器人

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

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

示例1：输入：grid=[[1,3,1],[1,5,1],[4,2,1]]输出：7

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

示例2：输入：grid=[[1,2,3],[4,5,6]]输出：12

提示：m==

n==grid[i].length

1=m,n=200

0=grid[i][j]=100

注意：本题与主站64题相同：

1、动态规划；O(n^2)，空间复杂度O(n^2)

funcminPathSum(grid[][]int)int{n:=len(grid)ifn==0{return0}m:=len(grid[0])dp:=make([][]int,n)fori:=0;in;i++{dp[i]=make([]int,m)}dp[0][0]=grid[0][0]fori:=0;in;i++{forj:=0;jm;j++{ifi==0&&j!=0{dp[i][j]=dp[i][j-1]+grid[i][j]}elseifi!=0&&j==0{dp[i][j]=dp[i-1][j]+grid[i][j]}elseifi!=0&&j!=0{dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]}}}returndp[n-1][m-1]}funcmin(a,bint)int{ifab{returnb}returna}

2、动态规划；O(n^2)，空间复杂度O(1)

funcminPathSum(grid[][]int)int{n:=len(grid)ifn==0{return0}m:=len(grid[0])fori:=0;in;i++{forj:=0;jm;j++{ifi==0&&j!=0{grid[i][j]=grid[i][j-1]+grid[i][j]}elseifi!=0&&j==0{grid[i][j]=grid[i-1][j]+grid[i][j]}elseifi!=0&&j!=0{grid[i][j]=min(grid[i-1][j],grid[i][j-1])+grid[i][j]}}}returngrid[n-1][m-1]}funcmin(a,bint)int{ifab{returnb}returna}

3、动态规划；O(n^2)，空间复杂度O(n)

funcminPathSum(grid[][]int)int{n:=len(grid)ifn==0{return0}m:=len(grid[0])dp:=make([]int,m)dp[0]=grid[0][0]fori:=1;im;i++{dp[i]=dp[i-1]+grid[0][i]}fori:=1;in;i++{dp[0]=dp[0]+grid[i][0]forj:=1;jm;j++{dp[j]=min(dp[j-1],dp[j])+grid[i][j]}}returndp[m-1]}funcmin(a,bint)int{ifab{returnb}returna}

4、递归；O(n^2)，空间复杂度O(n^2)

vararr[][]intfuncminPathSum(grid[][]int)int{n:=len(grid)ifn==0{return0}m:=len(grid[0])arr=make([][]int,n)fori:=0;in;i++{arr[i]=make([]int,m)}returndfs(grid,n-1,m-1)}funcdfs(grid[][]int,n,mint)int{ifm==0&&n==0{arr[0][0]=grid[0][0]returngrid[0][0]}ifn==0{returngrid[0][m]+dfs(grid,0,m-1)}ifm==0{returngrid[n][0]+dfs(grid,n-1,0)}ifarr[n][m]0{returnarr[n][m]}arr[n][m]=min(dfs(grid,n-1,m),dfs(grid,n,m-1))+grid[n][m]returnarr[n][m]}funcmin(a,bint)int{ifab{returnb}returna}

Medium题目，题目同leetcode64.最小路径和