[DP][数组]64. Minimum Path Sum

64. Minimum Path Sum

基础的DP。
给定mXn的二维数组，求(0,0) -->(m-1,n-1)路径的最小和。
思路：
建一个同样大小的二维数组，存(0,0)->当前点的最小和。

JAVA 31ms

class Solution {
    public int minPathSum(int[][] grid) {
        /*DP*/
        if(grid.length == 0)  return 0;
        int m = grid.length;
        int n = grid[0].length;
        int[][] sums = new int[m][n];
        
        sums[0][0] = grid[0][0];
        for(int i = 1; i <m; i++){
            sums[i][0] = grid[i][0] + sums[i-1][0];
        }
        for(int j = 1; j <n; j++){
            sums[0][j] = grid[0][j] + sums[0][j-1];
        }
        
        
        for(int i = 1; i<m ;i++){
            for(int j = 1; j<n ;j++){
                sums[i][j] = grid[i][j] + Math.min(sums[i-1][j],sums[i][j-1]);
            }
        }
        return sums[m-1][n-1];
    }
}

Python 74ms

class Solution(object):
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        if(len(grid) == 0):
            return 0
        sums = []
        m = len(grid)
        n = len(grid[0])
        sums.append([grid[0][0]])
        for i in range(1,m):
            list2D = [sums[i-1][0] + grid[i][0]]
            sums.append(list2D)
        for j in range(1,n):
            col2D = sums[0][j-1] + grid[0][j]
            sums[0].append(col2D)
            
        for i in range(1,m):
            for j in range(1,n):
                sums[i].append( min(sums[i-1][j], sums[i][j-1]) + grid[i][j] )
                
        return sums[m-1][n-1]
        

！ Python 48 ms solution 解

因为只查询最后一个，所以其实可以不用存mXn的一张表。
用滚动数组更快一些。

class Solution(object):
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        if not grid or not grid[0]:
            return 0
        row, col = len(grid), len(grid[0])
        sums = grid[0][:] # 复制第一行
        for c in range(1, col):
            sums[c] += sums[c - 1] #第c（1）行的baseline
            
        for r in range(1, row):
            new_sums = grid[r][:] # 复制第r行
            new_sums[0] += sums[0] # 第r行第一列的baseline
            for c in range(1, col):
                new_sums[c] = min(sums[c], new_sums[c - 1]) + grid[r][c]
            sums = new_sums
        return sums[-1]