2020.7.22&23

 

64. 最小路径和

简单的线性dp

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

python

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        n = len(grid)
        m = len(grid[0])
        dp = [grid[0][0]]
        for i in range(1, m):
            dp.append(dp[i-1] + grid[0][i])
        for i in range(1, n):
            for j in range(0, m):
                if j == 0:
                    dp[j] += grid[i][j]
                else:
                    dp[j] = min(dp[j-1], dp[j]) + grid[i][j]
        return dp[m-1]