牛客283182957号
牛客283182957号
全部
题解 | #矩阵的最小路径和#
全部文章
分类
题解(51)
归档
标签
去牛客网
登录
/
注册
题解 | #矩阵的最小路径和#
363 浏览
0 回复
2022-07-12
牛客283182957号
+关注
题目要求得到从「左上角」到「右下角」的
整个二维数组
的最小路径,因此其子问题为:对于二维数组中的每个元素位置,求取
从起点到该位置的最短路径
;
对于「右下角」的元素位置,从起点到该位置的最短路径即为最终答案。
或者要求到最右下元素(m,n)路径最小,那么到mn只能由m-1,n或m,n-1到达。子问题求解
m-1,n和m,n-1
。------------
》可以通过子问题求解就能够找到状态转移方程(递推方程)。
一个是状态方程,一个是递推边界。
举报
收藏
赞
评论加载中...