首页 > 代码库 > leetcode--Minimum Path Sum

leetcode--Minimum Path Sum

2024-07-07 08:57:49   225人阅读

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class Solution {
    /**This is a simple implementation of dynamic programming methodology. We use int[][] minGrid to denote the
     * minimum path sum from cell (0,0) to (i,j).
     * For each cell (i,j), there are two ways to reach it:
     * 1. go one step vertically from cell (i - 1 ,j)
     * 2. go one step horizontally from cell (i, j - 1).
     * 3. So the minimum path sum from cell (0,0) to (i,j) is
     *  minGrid[i][j] = min{grid[i][j] + minGrid[i - 1][j], grid[i][j] + minGrid[i][j - 1]};
     * @param grid
     * @return
     */
    public int minPathSum(int[][] grid) {
        int min = 0;
        int row = grid.length;
        if(row > 0){
            int column = grid[0].length;
            int[][] minGrid = new int[row][column];
            minGrid[0][0] = grid[0][0];
            for(int i = 1; i < row; ++i)
                minGrid[i][0] = grid[i][0]+ minGrid[i- 1][0];
            for(int i = 1; i < column; ++i)
                minGrid[0][i] = grid[0][i] + minGrid[0][i - 1];
            for(int i = 1; i < row; ++i){
                for(int j = 1; j < column; ++j)
                    minGrid[i][j] = Math.min(grid[i][j] + minGrid[i - 1][j], grid[i][j] + minGrid[i][j - 1]);
            }
            min = minGrid[row - 1][column - 1];
        }
        return min;    
    }
}

　　


联系
我们