leetcode解题: Minimum Path Sum (64)

发表于 | 分类于

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：DP O(N^2) with O(N) 空间

也是很直接的dp, dp[i][j]表示的是到(i,j)点的最小路径和。dp[i][j] = Min(dp[i - 1][j], dp[i][j -1]) + A[i][j]
最后的结果便是dp[n - 1][m - 1], 用滚动数组节省内存空间

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
public int minPathSum(int[][] grid) {
    
    if (grid == null || grid.length == 0) {
        return 0;
    }
    
    int nrow = grid.length;
    int ncol = grid[0].length;
    
    int[] dp = new int[ncol];
    dp[0] = grid[0][0];
    
    // Initialize the dp array
    for (int j = 1; j < ncol; j++) {
        dp[j] = dp[j - 1] + grid[0][j];
    }
        
    for (int i =  1; i < nrow; i++) {
        dp[0] += grid[i][0];
        for (int j = 1; j < ncol; j++) {
            dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
        }
    }
    
    return dp[ncol - 1];
}