0064-minimum-path-sum.adoc

64. Minimum Path Sum

{leetcode}/problems/minimum-path-sum/[LeetCode - Minimum Path Sum^]

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:

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

思考题：尝试使用一维数组做备忘录来实现一下。

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:

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

思路分析

一刷

link:{sourcedir}/_0064_MinimumPathSum.java[role=include]

二刷

link:{sourcedir}/_0064_MinimumPathSum_2.java[role=include]

参考资料

1. 64. 最小路径和 - 官方题解

2. 64. 最小路径和 - 动态规划，规范流程，清晰图解