编辑
2023-12-22
Leetcode
00
请注意,本文编写于 71 天前,最后修改于 71 天前,其中某些信息可能已经过时。

虽然看到1e9 + 7就知道要dp了,但我不知道怎么d

我首先的想法就是dp[i][j], 首先将matrix一维化,然后去记每个长度的最大值(如样例一样)。但这道题的范围1e5限制了我们只能至多O(nlogn)的范围内实现,而长度能最多从1到n,这样会导致我们的时间复杂度就会上升到1e10 (1e5 loop i, 1e5 loop j)很明显TLE了。

实际上我这样的想法将题目复杂化了(被样例骗了),我们不如换个想法给定一个起点i,j (即grid[i][j])我们去找它有多少increasing path,这样就能将复杂度降回O(n)。那么现在dp[i][j]现在就代表了从ij出发有多少increasing path, 但dp[i][j]和其他值的关系是什么呢?

从题目中我们可以得到有4个方向(上下左右),并且我们有strictly increasing的限制,这意味着我们不会有infinite loop的烦恼。更具体地,我们可以观测到,假设ij连接到ij+1这意味着dp[i][j] += dp[i][j+1]。这是为什么呢?我们如果假设dp[i][j+1]可以得到所有完整的increasing path,那么实际上我们除了需要在这每一个path上加上自己本身外,还有一个长度为一的自己。例如grid = [[1,1],[3,4]],dp[0][0]往下会得到[3] [3 4]两个值, 从grid[0][0]开始的话除了在他们之前添加本身外还有个自己,即[1] [1 3] [1 3 4]

所以我们最后的dp公式为dp[i][j] = 1加上其他满足increasing的条件的方向上的increasing path。

本文作者:Yorafa

本文链接:

版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!