Leetcode 每日一题：Longest Increasing Path in a Matrix
写在前面：
今天我们继续看一道 图论和遍历 相关的题目。这道题目的背景是在一个矩阵当中找寻最长的递增数列长度。思路上非常好想，绝对和 DFS 相关，但是题目的优化要求非常高，对于语言和内存特性的考察特别丰富，如果是单纯的 Leetcoder 或者是 扎根算法而语言相对专精较弱的同学，这道题目可能很难做到 AC，就让我们一起来看看吧！
题目介绍：
题目信息：
- 题目链接：https://leetcode.com/problems/longest-increasing-path-in-a-matrix/description/
- 题目类型：Array，Graph，DFS，Dynamic Programming(是的，可以拿 dp 做，但是太难了而且并不具备推广价值，所以不分享了)
- 题目难度：Hard（思路 easy，优化要求 hard）
- 题目来源：Google 高频面试真题
题目问题：
- 给定一个大小为 m * n 的矩阵，每一个矩阵的位置都代表一个 value
- 找出最长的 递增遍历行走路线
- 在行走的过程中，只能上下左右，不能走对角线
- 例子：
题目想法：
深度优先暴力解法：
一看到是走 “最长的递增” 数组，并且在图中只能上下左右移动，我们很容易可以想到 DFS，这也是一个标准的 DFS 问题。我们只需要遍历每一个位置当作起点，并且不断寻找周围有没有递增的位置可以让我们前进，返回当前起点所能达到的最大值。将所有的最大值统筹起来，进行返回。
很可惜，思路很美好，现实很骨感，这样的做法不仅会 TLE，而且会 MLE，在算法时间复杂度和占用空间内存的角度来讲都会爆炸。
Runtime：O(2^(m+n)) --> 我们需要遍历所有可能的子数组
Space：O(mn) --> 我们最坏需要遍历所有的 node 和 edge，并且，需要mn次 stack 来储存
太慢，也太耗空间了（如果懂得堆栈的小伙伴应该知道太多 recursion 会占掉很多内存）
时间复杂度优化：
暴力解法非常简单想到，那 Google 和 其他大厂的要求肯定不止这么一点儿～～ 但如果自己想想，我们每一次以一个点为起点进行探索的时候，我们的目标都是取得这个点所能创造的最大长度，从而决定我们是否有机会获得更好的结果。那我们是否可以利用 Memoization 的方法，将每个遍历过后的点的最大值记下来，这样之后的重复使用不就都不用再遍历了吗？
我们在从每一个点开始遍历 DFS 的时候，将所有路过的点的最大值进行一个更新，而我们在找寻起点的过程中，就可以直接从这些点里取值了，因为他一定是最大的。
为什么一定如果一个点被遍历过之后存下的结果一定 >= 我们以这个点为起点重新遍历呢？
- 如果这个点的现有最大值是从本点开始，那再来一次遍历也会得到相同结果
- 如果这个点的现有最大值是从一个比他更小的点得来的，那以他自己为起点此次结果一定会小于我们所存储的节点，因为单调递增的单向性
- 而这个点的现有最大值不可能来自己于一个比他更大的起点
- 所以总结，存下的结果 >= 以当前为起点遍历可能最大 ---> 当前存储的结果一定是最优的
Runtime：O(mn) ---> 我们只需要遍历一次图即可，可以被 AC
Space：O(mn) ---> 我们需要存储所有的矩阵点的最大值
内存优化：
虽然这道题的 O(mn) 的空间复杂度已经是最优复杂度了，但不同的 implementation 同样会导致 AC 和 MLE 的区别，题主自己在做这道题的时候，经过了算法的优化以后还是 MLE，后来经过对数据结构和 recursion 变量的优化才最终解决内存问题，这可能也是大厂对代码水平更高难度的考察吧，这也是我认为这道题是 hard 的一部分原因
如果使用 C++ 进行代码编写，可以优化的点有：
- 对于数据的存储，不使用 vector， 而是使用 dynamic array 进行内存分配
- 对于Recursion函数传入的矩阵和记忆矩阵，把他们变成 member variable，在recursion中静态调用，而不是不停的动态参数传入
第一个问题的原因是基于 vector 的特性。在 C++中，动态数组的内存分布并不是按照有多少个元素来分配的，而是分配 2^n 个储存空间，n 是让 2^n 大于所需长度的最小值。而这样的分配方式会造成内存浪费。例如：一个长度为 7 的 vector 实际上占用了 8 个长度的内存，而长度为 9 的 vector 实际上占用了 16 个长度的内存。而如果使用 dynamic allocation，在 matrix 长度宽度已知不会变的情况下，我们完全可以手动分配内存，精准的将 矩阵的维度 分配出来。在 2 个维度同时减少内存浪费，省去非常多的空间
第二个问题的原因是，没有一次 recursion function call，这个函数就会在内存中开辟一段储存空间，而如果我们将 矩阵和记忆矩阵作为变量不断传入，他们就会不断的在内存 stack 中生成很多很多 copy，从而导致 stack 崩掉。而如果我们将其改成 member variable，他们相对于所有的 recursion 函数就是全局的，每个 recursion 都只需要直接调用他的指针所指的真实数据，而不是 copy，这也会节省更多空间
在同时完成这两个优化以后，相信大家也能成功 AC 这道 Leetcode hard
题目代码：
class Solution {
public:
int x[4] = {0, 1, 0, -1};
int y[4] = {1, 0, -1, 0};
int** maxViewed; //use dynamic array instead of vector to prevent memory waste
int** matrix; //use member variable instead of arguement in recursion to prevent
//too much stack memory wasted in recursion
int DFS(int i, int j, int m, int n){
//we have already seen this point, so need to traverse.
if(maxViewed[i][j] != 0){
return maxViewed[i][j];
}
for(int d = 0; d < 4; d++){
int new_i = i + x[d];
int new_j = j + y[d];
//check in bound, no need to check revisit, but have check for increasing
if(new_i < m && new_i >= 0 && new_j < n && new_j >= 0){
if(matrix[i][j] < matrix[new_i][new_j]){
maxViewed[i][j] = max(DFS(new_i, new_j, m, n), maxViewed[i][j]);
}
}
}
maxViewed[i][j] += 1;
return maxViewed[i][j];
}
int longestIncreasingPath(vector<vector<int>>& matrix_target) {
int maxDist = 0;
int m = matrix_target.size(), n = matrix_target[0].size();
//create a cache and matrix storage for the traversing:
maxViewed = new int*[m]; // Allocate memory for rows
matrix = new int*[m];
for (int i = 0; i < m; ++i) {
maxViewed[i] = new int[n]; // Allocate memory for columns
matrix[i] = new int[n];
}
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
maxViewed[i][j] = 0;
matrix[i][j] = matrix_target[i][j];
}
}
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
maxDist = max(maxDist, DFS(i, j, m, n));
}
}
return maxDist;
}
};