2328. 网格图中递增路径的数目 - Kotlin 有向图的路径数量 二维DP

Problem: 2328. 网格图中递增路径的数目

思路

如果我们规定：矩阵中相邻的两个点，如果a严格大于b的话，构成一条b到a的原子路径，那么这道题可以理解为：给你一个有向图，求图中的所有路径数

由于题干限定了路径是必须是一条递增序列，因此可以保证图中不会出现环，即必定存在数个终点，自然地，这些终点应当是矩阵中的几个最大值

当考虑b->c这条路径时，对于任意c能到达的路径，显然b也是能够到达的，所以b能够到达的路径数量应当加上c能够到达的路径数量，以此类推，从一个点出发的路径数，应当为该点能够到达的相邻点的路径数之和加上它自己（即1），再以此类推，最终的递归会结束在上述的终点，由于终点没有任何能够到达的相邻点，因此从它们出发的路径数就是1

从该思路出发，我们应当将矩阵中的所有坐标按照数值的降序排序，即从终点出发反向进行广度优先搜索，一直搜索到起点（即几个最小值/没有入度的点 ）

设dp[r][c]为从点grid[r][c]出发的所有路径数，那么有

dp[r][c] += if (grid[r - 1][c] > grid[r][c]) dp[r - 1][c] else 0
dp[r][c] += if (grid[r + 1][c] > grid[r][c]) dp[r + 1][c] else 0
dp[r][c] += if (grid[r][c - 1] > grid[r][c]) dp[r][c - 1] else 0
dp[r][c] += if (grid[r][c + 1] > grid[r][c]) dp[r][c + 1] else 0

复杂度

• 时间复杂度:
• 空间复杂度:

Code

class Solution 
fun Solution.countPaths(grid: Array<IntArray>): Int {
    val pq = PriorityQueue<Pair<Int, Int>> { a, b -> grid[b.first][b.second] - grid[a.first][a.second] }
    val dp = Array(grid.size) { LongArray(grid[0].size) { 1 } }
    var sum: Long = 0
    for (r in grid.indices) {
        for (c in grid[0].indices) {
            pq.add(r to c)
        }
    }
    while (pq.isNotEmpty()) {
        val (r, c) = pq.remove()
        dp[r][c] = (dp[r][c] + if (r > 0                  && grid[r - 1][c] > grid[r][c]) dp[r - 1][c] else 0) % (1e9+7).toLong()
        dp[r][c] = (dp[r][c] + if (r < grid.size - 1      && grid[r + 1][c] > grid[r][c]) dp[r + 1][c] else 0) % (1e9+7).toLong()
        dp[r][c] = (dp[r][c] + if (c > 0                  && grid[r][c - 1] > grid[r][c]) dp[r][c - 1] else 0) % (1e9+7).toLong()
        dp[r][c] = (dp[r][c] + if (c < grid[0].size - 1   && grid[r][c + 1] > grid[r][c]) dp[r][c + 1] else 0) % (1e9+7).toLong()
        sum = (sum + dp[r][c]) % (1e9+7).toLong()
    }
    return sum.toInt()
}