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.

    Example 1:
    64. Minimum Path Sum - 图1
    Input: grid = [[1,3,1],[1,5,1],[4,2,1]] Output: 7 Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.
    Example 2:
    Input: grid = [[1,2,3],[4,5,6]] Output: 12

    Constraints:

    • m == grid.length
    • n == grid[i].length
    • 1 <= m, n <= 200
    • 0 <= grid[i][j] <= 100

    Runtime: 84 ms, faster than 69.24% of JavaScript online submissions for Minimum Path Sum.
    Memory Usage: 41.4 MB, less than 28.83% of JavaScript online submissions for Minimum Path Sum.

    1. /**
    2. * @param {number[][]} grid
    3. * @return {number}
    4. */
    5. var minPathSum = function(grid) {
    6. if (grid.length === 0) {
    7. return 0;
    8. }
    9. const m = grid.length;
    10. const n = grid[0].length;
    11. const dp = Array.from({ length: m })
    12. .map(_ => Array.from({ length: n }));
    13. dp[0][0] = grid[0][0];
    14. for (let i = 1; i < m; i++) {
    15. dp[i][0] = dp[i - 1][0] + grid[i][0];
    16. }
    17. for (let j = 1; j < n; j++) {
    18. dp[0][j] = dp[0][j - 1] + grid[0][j];
    19. }
    20. for (let i = 1; i < m; i++) {
    21. for (let j = 1; j < n; j++) {
    22. dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
    23. }
    24. }
    25. return dp[m - 1][n - 1];
    26. };