题目
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-path-sum
说明
每次只能向下或者向右移动一步。
示例:
- 输入
[
[1,3,1],
[1,5,1],
[4,2,1]
]
- 输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
思路
这是一道典型的动态规划问题（类似于Dijkstra算法算法）
-
图文解释
源代码
public static int minPathSum(int[][] grid) {
int columns = grid[0].length;
int rows = grid.length;
//使用以为数组存储更加节省空间
int[] value = new int[rows*columns];
value[0] = grid[0][0];
//存储列边界值
for (int i = 1; i < columns; i++) {
value[i] = value[i-1] + grid[0][i];
}
//存储行边界值
for (int i = 1; i < rows; i++) {
value[i*columns] = value[i*columns-columns] + grid[i][0];
}
//动态规划
for (int i = 1; i < rows; i++) {
for (int j = 1; j < columns; j++) {
value[i*columns+j] =grid[i][j] + Math.min(value[i*columns+j-1],value[(i-1)*columns+j]);
}
}
return value[rows*columns-1];
}
public static void main(String[] args) {
int[][] arr = {{1,7,1,2},{3,2,6,3},{5,1,4,1},{1,4,5,5}};
int result = minPathSum(arr);
System.err.println(result);
}
