minimum-path-sum.md

64. Minimum Path Sum - 最小路径和

Tags - 题目标签

Description - 题目描述

EN:

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:

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] <= 200

ZH-CN:

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

 

示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

 

提示：

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

Link - 题目链接

LeetCode - LeetCode-CN

Latest Accepted Submissions - 最近一次 AC 的提交

Language	Runtime	Memory	Submission Time
typescript	72 ms	43.8 MB	2022/04/14 13:54

/** 记忆化搜索 */
function minPathSum(grid: number[][]): number {
  const n = grid.length;
  const m = grid[0]?.length;

  // mem 存储访问过的路径最小值
  const mem = new Array(n).fill([]).map(i => new Array(m).fill(-1));

  function dfs(x, y): number {

    if (x === n - 1 && y === m - 1) {
       mem[x][y] = grid[x][y];
       return mem[x][y];
    }

    if (x === n - 1) {
       mem[x][y] = dfs(x, y + 1) + grid[x][y];
       return mem[x][y];
    } 

    if (y === m - 1) {
       mem[x][y] = dfs(x + 1, y) + grid[x][y];
       return mem[x][y];
    } 

    if (mem[x][y] !== -1) {
      return mem[x][y];
    }

    mem[x][y] = Math.min(dfs(x+1, y), dfs(x, y+1)) + grid[x][y];

    return mem[x][y];
  }

  return dfs(0, 0);
};

My Notes - 我的笔记

依然是典型的 dfs 记忆化搜索 / dp 双解法题