题目
给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
说明:每次只能向下或者向右移动一步。
示例:
1
2
3
4
5
6
7
8 输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/minimum-path-sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
首先考虑暴力破解:找到所有可能的路径,求和,找最小,时间复杂度$O(N^3)$。
- 这其中有没有重复计算?
有。
那么就动态规划,存储以当前位置为终点的最小路径和。
- 二维数组是否可以优化?
可以,因为只能向右或向下,所以只需要上一行的数据,空间复杂度可优化为$O(N)$。
状态转移方程:
$f(m,n)=min(f(m-1,n)+f(m,n-1))+x_{m,n}$
$x_{m,n}$为当前位置的值,$f(m,n)$为该位置的最小路径和;
下面考虑需要额外处理的情况:
- 边界情况:
第一行:每个位置的最小路径和为左侧所有数字包括自身之和;
第一列:每个位置的最小路径和为上方所有数字包括自身之和; - 特殊输入:
只有一行或只有一列:直接返回边界情况的求和结果。
代码:
1 | class Solution { |
- 能不能再优化?当前时间复杂度$O(MN)$,空间复杂度$O(N)$。
可以,直接原地修改数组,即在输入数组中直接存储最小路径和。空间复杂度$O(1)$。
总结
其实最后一步优化没想到。那么可以总结:对于一个需要执行某种操作的对象,空间复杂度最优一定是原地操作,比如快速排序法,就是在原地直接操作元素。