Java解决最小路径和
2023-12-16 21:36:46
Java解决最小路径和
01 题目
给定一个包含非负整数的 *m* x *n*
网格 grid
,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
**说明:**每次只能向下或者向右移动一步。
示例 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 == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 200
02 知识点
- 二维数组
- DP(动态规划)
03 我的题解
public class digui02 {
public static void main(String[] args) {
//测试
// int [][] grid =new int [][] {
// {1,3,1},
// {1,5,1},
// {4,2,1}
// };
int [][] grid =new int [][] {
{1,2,3},
{4,5,6},
};
minPathSum(grid);
}
public static int minPathSum(int[][] grid) {
//m表示二维数组的行数,n表示二维数组的列数
int m=grid.length;
int n=grid[0].length;
//用一个新的二维数组记录,走到当前格子最小的路径值
//路径值,在原数组中每个格子都有值,经过需要累加
int[][] nums=new int[m][n];
//从左上角出发,再不能绕路的前提下,只能从左或从上进入一格,因为第一行和第一列都是单边,所以独立赋值
nums[0][0]=grid[0][0];
for (int i = 1; i < m; i++) {
//原数组的基础上加上一格的数
nums[i][0]+=grid[i][0]+nums[i-1][0];
}
for (int j = 1; j < n; j++) {
nums[0][j]+=nums[0][j-1]+grid[0][j];
}
//和单边逻辑一样,但多一步比较,取较小值
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
nums[i][j]=grid[i][j]+Math.min(nums[i-1][j], nums[i][j-1]);
}
}
return nums[m-1][n-1];
}
}
文章来源:https://blog.csdn.net/2302_77182979/article/details/135037480
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!