64. Minimum Path Sum
給定一個大小為 m x n 的矩陣,找到從最左上角到最右下角的一條路徑,使得路徑上所
有元素的總和最小,路徑只能向下和向右移動。
Example:
https://assets.leetcode.com/uploads/2020/11/05/minpath.jpg
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.
思路:
1.任意一個點的總和必定是他的上面或左邊格子兩者最小路徑和加上當前元素,
可以使用動態規劃在兩者之中取較小的,遍歷完整個陣列後就可以求得解。
Java Code: