LeetCode : Minimum Path Sum #64
正刷着第64题没有思路的时候,翻看了一下Tips,这道题的方法和第62是如出一辙的,但是理解的方式不一样,在此做一个简单的记录,做一个笔记。
Question
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.
Analysis
我们简单分析一下,我们寻求的答案是寻求走完路径的最小和(每个方格上面有非负数)。
那么,也就是说,从第一步开始就要考虑下一步哪个数字最小,然后踩哪一块。
在走的路程中,全部选则最小的,那么他的和算起来就最小。
换言之,
1 | sum[i,j] = min(sum[i-1,j],sum[i,j-1]) + grid[i][j] |
其中,i和j分别为行和列,sum
为二维数组存储 i x j
方格中每一格中的最优步骤(最小数字)。
其他的和第62题如出一辙,只需要把第一行和第一列的每个方格的和遍历出来即可。
也就是说我们只需要维护这个二维数组,将每一个方格上最小数遍历出来存储在里面,然后取出 sum
中最后一行最后一列的数字即为题目所要求的答案。
接下来用 Java 写出整个思路。
Solution
1 | public class Solution { |
总结
搞懂了第64题,其实和第62题并没有什么太大的不同,只是换汤不换药罢了。
搞懂一道题,搞会一类题的精髓就在这里。
继续向前学习!