共计 1065 个字符，预计需要花费 3 分钟才能阅读完成。
动静布局的几个前提条件：
最优子结构性质
无后向性
子问题的重叠性
显然这道题是满足动静布局的解题条件的
每个门路的长度取决于之前门路的值
求解最大门路的过程中须要屡次用到之前求出的子门路的长度
易得状态转移方程为
当 i>0 且 j>0 时，
当 i 或 j 有一个等于 0 时，则无需思考子门路的抉择，即为
代码
func minPathSum(grid [][]int) int {
// 构建一个二维数组
m,n:=len(grid),len(grid[0])
order:=make([][]int,m)
for i:=range order{order[i]=make([]int,n)
}
// 计算门路长度
order[0][0]=grid[0][0]
for i:=1;i<n;i++{order[0][i]=order[0][i-1]+grid[0][i]
}
for i:=1;i<m;i++{order[i][0]=order[i-1][0]+grid[i][0]
}
for i:=1;i<m;i++{
for j:=1;j<n;j++{order[i][j]=grid[i][j]+min(order[i-1][j],order[i][j-1])
}
}
return order[m-1][n-1]
}
func min(a int,b int)int{if a<b {return a}
return b
}
成果
此时
工夫复杂度：O(mn)，其中 m 和 n 别离是网格的行数和列数。须要对整个网格遍历一次，计算 dp 的每个元素的值。
空间复杂度：O(mn)，其中 m 和 n 别离是网格的行数和列数。创立一个二维数组 dp，和网格大小雷同。
空间复杂度能够优化，例如每次只存储上一行的 \textit{dp}dp 值，则能够将空间复杂度优化到 O(n)O(n)
代码
func minPathSum(grid [][]int) int {
// 构建一个二维数组
m,n:=len(grid),len(grid[0])
last:=make([]int,n)
now:=make([]int,n)
last[0]=grid[0][0]
for i:=1;i<n;i++{last[i]=last[i-1]+grid[0][i]
}
now=last
for i:=1;i<m;i++{now[0]=last[0]+grid[i][0]
for j:=1;j<n;j++{now[j]=grid[i][j]+min(last[j],now[j-1])
}
last=now
}
return now[n-1]
}
func min(a int,b int)int{if a<b {return a}
return b
}成果
正文完