36.Minimum Path Sum（最小路径和）

Level：

Medium

题目描述：

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.

Example:

Input:

[

  [1,3,1],

  [1,5,1],

  [4,2,1]

]

Output: 7

Explanation: Because the path 1→3→1→1→1 minimizes the sum.

思路分析：

题目要求找出从矩阵的左上角到右下角最短的路径长度，我们可以采用动态规划的思想求解，我们用dp[ i ] [ j ]来表示走到第i行和第j列的最短路径长度。由题意知，机器人只能向右和向下走，那么状态转移方程是 dp[ i ] [ j ]=min（dp [i-1] [ j ]，dp[ i ] [ j-1]）+grid[ i ] [ j ]。注意到矩阵第一行或者第一列某个位置，路径只有一条。（因为起点是左上角，并且只能向右向下移动）

代码：

public class Solution{

    public int minPathSum(int [][]grid){

        if(grid==null||grid.length==0)

            return 0;

        int [][]dp=new int [grid.length][grid[0].length];

        int i,j;

        dp[0][0]=grid[0][0];

        for(i=1;i<grid.length;i++){

            dp[i][0]=dp[i-1][0]+grid[i][0];

        }

        for(j=1;j<grid[0].length;j++){

            dp[0][j]=dp[0][j-1]+grid[0][j];

        }

        for(i=1;i<grid.length;i++){

            for(j=1;j<grid[0].length;j++){

                dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];

            }

        }

        return dp[i-1][j-1];

    }

}

巴特西

36.Minimum Path Sum（最小路径和）

Level：

题目描述：

思路分析：

代码：

最新文章

热门文章