L1-最短路径和

Posted on |

给定一个只含非负整数的m*n网格，找到一条从左上角到右下角的可以使数字和最小的路径。

代码

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
public class Solution {
    /**
     * @param grid: a list of lists of integers
     * @return: An integer, minimizes the sum of all numbers along its path
     */
 public int minPathSum(int[][] grid) {
        // write your code here
    	int m=grid.length;
    	int n=grid[0].length;
    	int[][] dp=new int[m][n];
    	dp[0][0]=grid[0][0];
        for(int i=0;i<m-1;i++)
        	dp[i+1][0]=grid[i+1][0]+dp[i][0];
        for(int j=0;j<n-1;j++)
        	dp[0][j+1]=grid[0][j+1]+dp[0][j];
        for(int i=0;i<m-1;i++)
        	for(int j=0;j<n-1;j++)
        	{
        		dp[i+1][j+1]=grid[i+1][j+1]+min(dp[i][j+1],dp[i+1][j]);
        	}
        return dp[m-1][n-1];
    }

	private int min(int i, int j) {
		// TODO 自动生成的方法存根
		return i<j?i:j;
		
	}
}

思路

dp[ i+1 ][ j+1 ] = min( dp [ i+1 ][ j ] , dp[ i ][ j+1 ] ) + grid[ i ][ j ]

时间复杂度 O（nm）， 空间复杂度 O（nm）

参考链接

https://blog.csdn.net/chan15/article/details/48914325