算法动态规划

优先级队列优化 DP

字数统计: 2.2k字   |   阅读时长: 9分
, , , ,

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

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

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

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

本题在状态推导过程中，维护状态转移时的各种决策用的数据结构是优先级队列，因此这可以作为一个优先级队列优化 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