首页 > 代码库 > LeetCode Minimum Path Sum

LeetCode Minimum Path Sum

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 public class Solution { 2     public int minPathSum(int[][] grid) { 3             if (grid==null) { 4                 return 0; 5             } 6             int minpath=0; 7             int m=grid.length; 8             int n=grid[0].length; 9             int[][] sumpath=new int[m][n];10             sumpath[0][0]=grid[0][0];11         for (int j = 1; j < n; j++) {12             sumpath[0][j]=sumpath[0][j-1]+grid[0][j];13         }14         15         for (int i = 1; i < m; i++) {16             sumpath[i][0]=sumpath[i-1][0]+grid[i][0];17         }18         19         for (int i = 1; i < m; i++) {20             for (int j = 1; j < n; j++) {21                 sumpath[i][j]=grid[i][j]+Math.min(sumpath[i][j-1], sumpath[i-1][j]);22             }23         }24         25         return sumpath[m-1][n-1];26     }27 }

 

LeetCode Minimum Path Sum