【LeetCode】64

64. 最小路径和

ts

function minPathSum(grid: number[][]): number {
    const m = grid.length
    const n = grid[0].length
    // 只有一行或一列
    if (m == 1) {
        let sum = 0
        for (let i = 0; i < n; i++) {
            sum += grid[0][i]
        }
        return sum
    }
    if (n == 1) {
        let sum = 0
        for (let i = 0; i < m; i++) {
            sum += grid[i][0]
        }
        return sum
    }
    // 行累加
    for (let i = 1; i < m; i++) {
        grid[i][0] += grid[i - 1][0]
    }
    // 列累加
    for (let i = 1; i < n; i++) {
        grid[0][i] += grid[0][i - 1]
    }
    // 运行中间部分
    for (let i1 = 1; i1 < m; i1++) {
        for (let i2 = 1; i2 < n; i2++) {
            grid[i1][i2] = grid[i1][i2] + Math.min(grid[i1 - 1][i2], grid[i1][i2 - 1])
        }
    }
    return grid[m - 1][n - 1]
};

C#

public class Solution {
    public int MinPathSum(int[][] grid) {
        int m = grid.Length;
        int n = grid[0].Length;
        int[,] dp = new int[m,n];
        dp[0,0] = grid[0][0];
        for(int i=1;i
            dp[i,0] = grid[i][0]+dp[i-1,0];
        }
        for(int i=1;i
            dp[0,i] = grid[0][i]+dp[0,i-1];
        }
        if(m==1){
            return dp[0,n-1];
        }
        if(n==1){
            return dp[m-1,0];
        }
        for(int i1 = 1;i1
            for(int i2 = 1;i2
                dp[i1,i2] = grid[i1][i2] + Math.Min(dp[i1-1,i2],dp[i1,i2-1]);
            }
        }
        return dp[m-1,n-1];
    }
}

public class Solution {
    public int MinPathSum(int[][] grid) {
        int m = grid.Length;
        int n = grid[0].Length;
        for(int i=1;i
            grid[i][0] += grid[i-1][0];
        }
        for(int i=1;i
            grid[0][i] += grid[0][i-1];
        }
        if(m==1){
            return grid[0][n-1];
        }
        if(n==1){
            return grid[m-1][0];
        }
        for(int i1 = 1;i1
            for(int i2 = 1;i2
                grid[i1][i2] += Math.Min(grid[i1-1][i2],grid[i1][i2-1]);
            }
        }
        return grid[m-1][n-1];
    }
}

java

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

python

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