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

leetcode 64 Minimum Path Sum ----- java

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.

还是之前题的延伸,求最小路径。还是可以在之前的版本上延伸。其实都是62题的变种,理解了dp,其实就都不难。

public class Solution {    public int minPathSum(int[][] grid) {        int m = grid.length;        int n = grid[0].length;        if( m == 0 || n == 0)            return 0;        int result = 0;        if( m == 1){            for( int i = 0;i<n;i++)                result+=grid[0][i];            return result;        }        if( n == 1){            for( int i = 0;i<m;i++){                result += grid[i][0];            }            return result;        }        int[] dp = new int[n];        dp[0] = grid[0][0];        for( int i = 1 ;i<n;i++){            dp[i] = dp[i-1]+grid[0][i];        }        for( int i = 1;i<m;i++){            dp[0] = dp[0]+grid[i][0];            for( int j = 1;j<n;j++){                dp[j] = dp[j]>dp[j-1]?dp[j-1]+grid[i][j]:dp[j]+grid[i][j];            }        }        return dp[n-1];                                    }}

 

leetcode 64 Minimum Path Sum ----- java