https://leetcode.cn/problems/maximum-strictly-increasing-cells-in-a-matrix/

斐波那契数列

求斐波那契数列第 i 项
递归解法

int solve(int i) {
    return i <= 1 ? 1 : (solve(i - 1) + solve(i - 2));
}

记忆化搜索解法

int f[100];
int solve(int i) {
    if (!f[i]) {
        f[i] = i <= 1 ? 1 : (solve(i - 1) + solve(i - 2));
    }
    return f[i];
}

递推（动态规划）解法

int f[100];
int solve(int i) {
    f[0] = f[1] = 1;
    for (int j = 2; j <= i; i++) {
        f[j] = f[j - 1] + f[j - 2];
    }
    return f[i];
}

记忆化搜索 = 深度优先搜索的实现 + 动态规划的思想

滑雪

题目描述：Michael 喜欢滑雪。这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael 想知道在一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。

int n, m;
vector<vector<int>> dis;
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
void dfs(int x, int y, vector<vector<int>>& mat) {
    for (int k = 0; k < 4; k++) {
        int tx = x + dx[k], ty = y + dy[k];
        if (mat[tx][ty] >= mat[x][y]) continue;
        if (!dis[tx][ty]) dfs(tx, ty, mat);
        dis[x][y] = max(dis[x][y], dis[tx][ty] + 1);
    }
    if (!dis[x][y]) dis[x][y] = 1;
}
int maxDecreasingCells(vector<vector<int>>& mat) {
    n = mat.size(), m = mat[0].size();
    dis.resize(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!dis[i][j]) dfs(i, j, mat);
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            ans = max(ans, dis[i][j]);
        }
    }
    return ans;
}

看这道题

TLE做法

《滑雪增强版》，滑雪不是搜索了周围的4个点吗，改一下 dfs 的实现，搜一下当前行列所有点就行，easy！

    void dfs(int x, int y, vector<vector<int>>& mat) {
        for (int k = 0; k < n; k++) {
            int tx = k, ty = y;
            if (tx == x) continue;
            if (mat[tx][ty] <= mat[x][y]) continue;
            if (!dis[tx][ty]) dfs(tx, ty, mat);
            dis[x][y] = max(dis[x][y], dis[tx][ty] + 1);
        }
        for (int k = 0; k < m; k++) {
            int tx = x, ty = k;
            if (ty == y) continue;
            if (mat[tx][ty] >= mat[x][y]) continue;
            if (!dis[tx][ty]) dfs(tx, ty, mat);
            dis[x][y] = max(dis[x][y], dis[tx][ty] + 1);
        }
        if (!dis[x][y]) dis[x][y] = 1;
    }

复杂度分析
计算每个点的答案时会遍历一遍，复杂度为总点数 O(n*m)
每个点在计算时会遍历行与列，复杂度为O(n+m)
合起来 O(n*m*(n+m))，10^{10}

分析搜索过程

每个点在遍历行与列时只会查找比它大的点，并用其中记录的 最大值+1 更新当前点的值
ans[i][j] = max(max(ans[l][j]), max(ans[i][r])) + 1
搜索过程是具有单调性的，与斐波那契数列递推做法类似，假如先对矩阵中所有点从大到小进行排序，并按顺序遍历，那么在计算某个点时，这时候比它大的点都已经计算完成，就不需要往下进行搜索了。这时候我们只需要处理计算过的答案中行与列中的最大值即可，用两个数组维护行与列的最大答案。
更新与查询都可以做到O(1)，总复杂度为排序的复杂度和遍历每个点的复杂度O(n*m*log_2(n*m)+n*m) 。

    int n, m;
    vector<vector<int>> dis;
    struct point {
        int x, y, v;
        bool operator<(const point& f) {
            return v > f.v;
        }
    };
    int maxIncreasingCells(vector<vector<int>>& mat) {
        n = mat.size(), m = mat[0].size();
        dis.resize(n, vector<int>(m, 0));
        vector<point> p;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                p.emplace_back((point){i, j, mat[i][j]});
            }
        }
        vector<int> l(n, 0), r(m, 0);
        sort(p.begin(), p.end());
        for (int i = 0; i < n * m; i++) {
            int res = max(l[p[i].x], r[p[i].y]) + 1;
            l[p[i].x] = max(l[p[i].x], res);
            r[p[i].y] = max(r[p[i].y], res);
        } 

        int ans = 0;
        for (int i = 0; i < n; i++) ans = max(ans, l[i]);
        for (int j = 0; j < m; j++) ans = max(ans, r[j]);
        return ans;
    }

最终解法

到这一步仍有一点小问题，题目中要求路径严格递增，所以等值相同的节点都计算完之后再一同更新。这里的方法就非常多了，提供一个解决方法：

    int n, m;
    vector<vector<int>> dis;
    struct point {
        int x, y, v;
        bool operator<(const point& f) {
            return v > f.v;
        }
    };
    struct option {
        int op, id, v;
    };
    int maxIncreasingCells(vector<vector<int>>& mat) {
        n = mat.size(), m = mat[0].size();
        vector<point> p;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                p.emplace_back((point){i, j, mat[i][j]});
            }
        }
        vector<int> l(n, 0), r(m, 0);
        sort(p.begin(), p.end());
        queue<option> q;
        for (int i = 0; i < n * m; i++) {
            int res = max(l[p[i].x], r[p[i].y]) + 1;
            q.push((option){1, p[i].x, res});
            q.push((option){0, p[i].y, res});
            if (i == n * m - 1 || p[i + 1].v != p[i].v) {
                while (!q.empty()) {
                    option f = q.front();
                    q.pop();
                    if (f.op == 1) {
                        l[f.id] = max(l[f.id], f.v);
                    } else {
                        r[f.id] = max(r[f.id], f.v);
                    }
                }
            }
        } 

        int ans = 0;
        for (int i = 0; i < n; i++) ans = max(ans, l[i]);
        for (int j = 0; j < m; j++) ans = max(ans, r[j]);
        return ans;
    }