MinimumPathSum坐标型的二维动态规划
程序员文章站
2022-06-23 12:04:32
Given amxngrid filled with non-negative numbers, find a path from top left to bottom right which...
Given amxngrid filled with non-negative numbers, find a path from top left to bottom right whichminimizesthe sum of all numbers along its path.
这是一个坐标型的二维动态规划,需要注意的是:坐标不一定是正方形,也有可能是矩形
java
public class Solution { /* * @param grid: a list of lists of integers * @return: An integer, minimizes the sum of all numbers along its path */ public int minPathSum(int[][] grid) { // write your code here if (grid == null || grid.length == 0) { return -1; } if (grid[0] == null || grid[0].length == 0) { return -1; } // state int m = grid.length; int n = grid[0].length; int[][] f = new int[m][n]; // initialize f[0][0] = grid[0][0]; for (int i = 1; i < m; i++) { f[i][0] = f[i - 1][0] + grid[i][0]; } for (int i = 1; i < n; i++) { f[0][i] = f[0][i - 1] + grid[0][i]; } // function for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { f[i][j] = grid[i][j] + Math.min(f[i - 1][j], f[i][j - 1]); } } // answer return f[m - 1][n - 1]; } }