今天再LeetCode做每日一题的时候，遇到了下面的一道题。
https://leetcode-cn.com/problems/minimum-path-sum/
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
输入:
[[1,3,1],[1,5,1],[4,2,1]]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
看到这里，我想了一下，大概是Dijsktra算法的问题，然后就立刻开始写了下去。
下边是我按照这道题写的Dijsktra算法的解法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| class Dijkstra
{
int[,] dijkstraArray;
int lengthr, lengthc;
private void FindMinPos(out int r, out int c)
{
int min = 65535;
r = -1;
c = -1;
for (int i = 0; i < lengthr; i++)
{
for (int j = 0; j < lengthc; j++)
{
if (dijkstraArray[i, j] > -1 && dijkstraArray[i, j] <= min)
{
min = dijkstraArray[i, j];
r = i;
c = j;
}
}
}
}
public int MinPathSum(int[][] grid)
{
lengthr = grid.Length;
lengthc = grid[0].Length;
dijkstraArray = new int[lengthr, lengthc];
for (int i = 0; i < dijkstraArray.GetLength(0); i++)
{
for (int j = 0; j < dijkstraArray.GetLength(1); j++)
{
dijkstraArray[i, j] = -1;
}
}
dijkstraArray[0, 0] = grid[0][0];
while (true)
{
FindMinPos(out int r, out int c);
if (lengthc - 1 == c && lengthr - 1 == r) break;
if (c < lengthc - 1)
{
if (-1 != dijkstraArray[r, c + 1]) dijkstraArray[r, c + 1] = (dijkstraArray[r, c + 1] < dijkstraArray[r, c] + grid[r][c + 1]) ? dijkstraArray[r, c + 1] : dijkstraArray[r, c] + grid[r][c + 1];
else dijkstraArray[r, c + 1] = dijkstraArray[r, c] + grid[r][c + 1];
}
if (r < lengthr - 1)
{
if (-1 != dijkstraArray[r + 1, c]) dijkstraArray[r + 1, c] = (dijkstraArray[r + 1, c] < dijkstraArray[r, c] + grid[r + 1][c]) ? dijkstraArray[r + 1, c] : dijkstraArray[r, c] + grid[r + 1][c];
else dijkstraArray[r + 1, c] = dijkstraArray[r, c] + grid[r + 1][c];
}
dijkstraArray[r, c] = -1;
}
return dijkstraArray[lengthr - 1, lengthc - 1];
}
}
|
于是就非常自信的提交了。
结果。。
| 提交结果 | 运行时间 | 内存消耗 | 语言 |
|---|
| 超出时间限制 | N/A | N/A | Csharp |
我点进去看发现，60 / 61 个通过测试用例
最后执行的输入：因为它实在是ta~~~~~~~~i长了，这个页面放了会卡，所以我放在了这个页面。
what？超出时间限制我能理解，但是这个我实在是想不出来办法对它做太多优化。
于是我就去看评论，发现这根本就不是我想的这种Dijsktra解决的最短路径问题。
我学到了一个新的名词：动态规划。
这是竟然是一道动态规划问题，而且这个名词我还真没听说过，(也有可能听说过但是忘记了)，我可能真的需要重新认真学习一边数据结构与算法了。
评论中翻到一个比较短的代码，我复现了一下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
public int MinPathSum2(int[][] grid)
{
lengthr = grid.Length;
lengthc = grid[0].Length;
for (int r = 1; r < lengthr; r++)
{
grid[r][0] += grid[r - 1][0];
}
for (int c = 1; c < lengthc; c++)
{
grid[0][c] += grid[0][c - 1];
}
for (int r = 1; r < lengthr; r++)
{
for (int c = 1; c < lengthc; c++)
{
grid[r][c] += Math.Min(grid[r - 1][c], grid[r][c - 1]);
}
}
return grid[lengthr - 1][lengthc - 1];
}
|
看到这段代码，我首先的感觉是不可能，这不就是个局部最优解问题么，肯定有问题。
抱着这种想法，我尝试了多组数据进行试验，想要验证我的这个想法。
最终我失败了，我承认这种方法非常有效。但是我不太能理解这种方法。。。
为什么这样计算就能算出来结果。
我尝试用纸模拟这种算法，意外的发现，如果我在arr[1,1]开始的数组计算最小值时候，如果不是按照每一行的顺序，就会对结果产生影响。
比如下边一个例子：
其最短路径应为红色标注内容
按照上述代码执行完arr[0,i]和arr[i,0]后，剩下的部分应该是
此时应该对arr[1,1]开始进行计算最小值，但是如果我此时直接计算arr[1,2]的值的话，会对结果产生影响。
※对这种影响进行分析，我发现一个道理，在这个数组中，按照顺序进行计算的话，每一个待处理的点所对应的前两个内容是保存了一定的前人的信息的，这两个点绝对不是只代表了自己的值。
明白了这个问题之后，我发现自己还是不太明白这么写的逻辑含义，只是能认同这个程序是可以解决问题的了。
于是我去寻求已婚的Bilibili大学的教授们求助。
发现了这个视频：av18512769
里边讲到的第二个问题的第二种解法应用的就是这种思想。
日期：2020年7月23日
该文章内容尚未完结，随着后期学习会继续更新，请注意！
参考链接
LeetCode原题目：https://leetcode-cn.com/problems/minimum-path-sum/
BiliBili教程：https://www.bilibili.com/video/av18512769
