首页 > 代码库 > 【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.


题解:类似Unique Paths这道题,只是初始化和更新answer数组的方式不同。

代码如下(Java):

 1 public class Solution { 2     public int minPathSum(int[][] grid) { 3         int m = grid.length; 4         int n = grid[0].length; 5         int[][] answer = new int[m][n]; 6          7         answer[0][0] = grid[0][0]; 8         for(int i = 1;i < m;i++) 9             answer[i][0] = answer[i-1][0] + grid[i][0];10         for(int i = 1;i < n;i++)11             answer[0][i] = answer[0][i-1] + grid[0][i];12         13         14         for(int i = 1;i < m;i++)15         {16             for(int j = 1;j < n;j++){17                 answer[i][j] = Math.min(answer[i-1][j],answer[i][j-1])+grid[i][j] ;18             }19         }20         21         return answer[m-1][n-1];22     }23 }