【数据结构优化DP】力扣2617-网格图中最少访问的格子数

  |  

摘要: 堆优化 DP、自定义堆的比较规则

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


各位好,本文我们解决一个在棋盘上可以向下或向右行动的问题。本题的特点是每一步可以在给定范围内跳格子行动,而不一定要走到相邻格子。

这种在棋盘上行动的问题,之前我们处理的比较多的是只能走到相邻格子的情况。而本题这种可以跳着走的情况,如果再用棋盘 DP 的思路,就会发现在状态转移的时候,可能的决策数量很多(只能走到相邻格子的情况,可能的决策就只有两种),因此时间复杂度就会很大,需要仔细分析状态转移时的决策,看看哪些决策是可以通过数据结构优化掉的。

$1 题目

给你一个下标从 0 开始的 m x n 整数矩阵 grid 。你一开始的位置在 左上角 格子 (0, 0) 。

当你在格子 (i, j) 的时候,你可以移动到以下格子之一:

  • 满足 j < k <= grid[i][j] + j 的格子 (i, k) (向右移动),或者
  • 满足 i < k <= grid[i][j] + i 的格子 (k, j) (向下移动)。

请你返回到达 右下角 格子 (m - 1, n - 1) 需要经过的最少移动格子数,如果无法到达右下角格子,请你返回 -1 。

提示:

1
2
3
4
5
6
m == grid.length
n == grid[i].length
1 <= m, n <= 1e5
1 <= m * n <= 1e5
0 <= grid[i][j] < m * n
grid[m - 1][n - 1] == 0

示例 1:

输入:grid = [[3,4,2,1],[4,2,3,1],[2,1,0,0],[2,4,0,0]]
输出:4
解释:上图展示了到达右下角格子经过的 4 个格子。
示例 2:

输入:grid = [[3,4,2,1],[4,2,1,1],[2,1,1,0],[3,4,1,0]]
输出:3
解释:上图展示了到达右下角格子经过的 3 个格子。
示例 3:

输入:grid = [[2,1,0],[1,0,0]]
输出:-1
解释:无法到达右下角格子。

$2 题解

算法:动态规划

定义 $dp[i][j]$ 表示从 $(0, 0)$ 走到 $(i, j)$ 的最少步数。这样我们要求的是 $dp[m-1][n-1]$。

对于 $(i, j)$,我们考虑从哪些格子走一步之后可以到达 $(i, j)$。有两个可能的方向:

  • 一个是从左边来,也就是从 $(i, a)$ 到 $(i, j)$,其中 $a \geq 0$ 且 $a < j \leq grid[i][a] + a$。
  • 一个是从上边来,也就是从 $(a, j)$ 到 $(i, j)$,其中 $a \geq 0$ 且 $a < j \leq grid[a][j] + a$。

由于在动态规划推导时, $dp[i][j]$ 只有可能从其左边的格子或上边的格子转移过来,因此按照 $i=0,1,\cdots,m-1$, $j=0,1,\cdots,n-1$ 的顺序推导 $dp[i][j]$,在推导 $dp[i][j]$ 时,所有可能的上一阶段的状态就都是已经推导完成的了。

线性地推导 $i, j$,状态转移方程如下:

数据结构优化 DP (最小堆)

在推导 $dp[i][j]$ 时,如果每个决策都考虑一遍,时间复杂度无法接受。因此我们看看能不能根据状态转移方程的特点,通过数据结构优化。

可以看到,有两个方向的决策可以到达 $dp[i][j]$,一个是从左边来,也就是 $dp[i][a], 0 \leq a < j$,此时左边的这些状态已经推导完了,是已知的。我们需要的是这些 $dp$ 值中的最小值。因此优化状态转移过程的数据结构可以选择最小堆。

但是这里还有个条件,就是 $a + grid[i][a] \geq j$,如果不满足这一点的话,$dp[i][a]$ 就无法转移到 $dp[i][j]$,这对于 $dp[i][j]$ 以及后续要推导的状态来说,就是一个不可行的决策。

基于以上分析,状态转移过程就可以描述出来了:

  • 按照外层 i 从小到大、内层 j 从小到大的顺序推导状态。假设当前推导到 dp[i][j],此时左边和上边的状态已经推导完成。
  • 推导过程中,每一行和每一列都维护一个最小堆,row_heaps[i] 表示第 i 行的最小堆 ,col_heaps[j] 表示第 j 列的最小堆,推导到 dp[i][j] 时,row_heaps[i] 中维护着 dp[i][0..j-1] 中的状态值、col_heaps[j] 中维护着 dp[0..i-1][j] 中的状态值。
  • 考察 row_heaps[i] 的堆顶,假设其代表 dp[i][a],如果 a + grid[i][a] < j,则 dp[i][a] 无法转移到 dp[i][j],那它肯定也不可能转移到更右边的状态。因此它在后续的状态推导中就是一个无效的决策,直接弹出,继续考察下一个。直至堆顶满足 a + grid[i][a] >= j 的,或者堆空为止。若堆空说明 dp[i][j] 是无法从左侧的状态转移来的。
  • 考察 col_heaps[j] 的堆顶,逻辑类似。弹出堆顶直至堆顶满足 a + dp[a][j] >= i,或堆空为止。
  • 根据上两步中得到的内容,就可以根据状态转移方程得到 dp[i][j] 了。将 dp[i][j] 分别压入 row_heaps[i]col_heaps[j],即可推导下一个状态了。

一共有 $O(mn)$ 个状态需要推导,每个状态推导时,处理决策的时间复杂度就是堆的压入弹出,每个状态都需要压入两个堆,并且最多弹出一次,因此时间复杂度分别为 $O(\log n)$ 和 $O(\log m)$,总时间复杂度为 $O(mn(\log n + \log m))$。

最后需要注意的是堆中元素中要记录的信息,row_heaps[i] 中记录 dp[i][j], j 两条信息;col_heaps[j] 中记录 dp[i][j], i 两条信息。

代码 (C++)

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <queue>
#include <vector>
#include <climits>


struct Item
{
int dp, idx;
Item(){}
Item(int dp, int idx):dp(dp),idx(idx){}
};

struct HeapCmp
{
bool operator()(const Item& i1, const Item& i2) const
{
return i1.dp > i2.dp;
}
};

class Solution {
public:
int minimumVisitedCells(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();

vector<priority_queue<Item, vector<Item>, HeapCmp>> row_heaps(m);
vector<priority_queue<Item, vector<Item>, HeapCmp>> col_heaps(n);

vector<vector<int>> dp(m, vector<int>(n, -1));
dp[0][0] = 0;
row_heaps[0].push(Item(dp[0][0], 0));
col_heaps[0].push(Item(dp[0][0], 0));

for(int i = 0; i < m; ++i)
for(int j = 0; j < n; ++j)
{
if(i == 0 && j == 0)
continue;
int minx = INT_MAX / 2;
while(!row_heaps[i].empty())
{
Item top_item = row_heaps[i].top();
if(top_item.idx + grid[i][top_item.idx] < j)
row_heaps[i].pop();
else
{
minx = min(minx, top_item.dp);
break;
}
}
while(!col_heaps[j].empty())
{
Item top_item = col_heaps[j].top();
if(top_item.idx + grid[top_item.idx][j] < i)
col_heaps[j].pop();
else
{
minx = min(minx, top_item.dp);
break;
}
}
if(minx != INT_MAX / 2)
{
dp[i][j] = minx + 1;
row_heaps[i].push(Item(dp[i][j], j));
col_heaps[j].push(Item(dp[i][j], i));
}
}
if(dp[m - 1][n - 1] == -1)
return -1;
return dp[m - 1][n - 1] + 1;
}
};

代码 (Python)

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
import heapq

INF = int(1e10)

class Item:
def __init__(self, dp, idx):
# 对于 row_heaps[i], idx 代表 j
# 对于 col_heaps[j], idx 代表 i
self.dp = dp
self.idx = idx

def __lt__(self, other):
return self.dp < other.dp

class Solution:
def minimumVisitedCells(self, grid: List[List[int]]) -> int:
m = len(grid)
n = len(grid[0])

row_heaps = [[] for _ in range(m)]
col_heaps = [[] for _ in range(n)]

dp = [[-1 for _ in range(n)] for _ in range(m)]
dp[0][0] = 0
heapq.heappush(row_heaps[0], Item(dp[0][0], 0))
heapq.heappush(col_heaps[0], Item(dp[0][0], 0))

for i in range(m):
for j in range(n):
if i == 0 and j == 0:
continue
minx = INF
while row_heaps[i]:
top_item = row_heaps[i][0]
if top_item.idx + grid[i][top_item.idx] < j:
heapq.heappop(row_heaps[i])
else:
minx = min(minx, top_item.dp)
break
while col_heaps[j]:
top_item = col_heaps[j][0]
if top_item.idx + grid[top_item.idx][j] < i:
heapq.heappop(col_heaps[j])
else:
minx = min(minx, top_item.dp)
break
if minx != INF:
dp[i][j] = minx + 1
if dp[i][j] != -1:
heapq.heappush(row_heaps[i], Item(dp[i][j], j))
heapq.heappush(col_heaps[j], Item(dp[i][j], i))

return dp[m-1][n-1] + 1 if dp[m-1][n-1] != -1 else -1

Share