侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【动态规划】矩阵中和能被 K 整除的路径【力扣第 314 场周赛】

GabrielxD
2022-10-09 / 0 评论 / 0 点赞 / 45 阅读 / 978 字 / 正在检测是否收录...

题目

6203. 矩阵中和能被 K 整除的路径


给你一个下标从 0 开始的 m x n 整数矩阵 grid 和一个整数 k 。你从起点 (0, 0) 出发,每一步只能往  或者往  ,你想要到达终点 (m - 1, n - 1) 。

请你返回路径和能被 k 整除的路径数目,由于答案可能很大,返回答案对 10^9 + 7 取余 的结果。

示例 1:

输入:grid = [[5,2,4],[3,0,5],[0,7,2]], k = 3
输出:2
解释:有两条路径满足路径上元素的和能被 k 整除。
第一条路径为上图中用红色标注的路径,和为 5 + 2 + 4 + 5 + 2 = 18 ,能被 3 整除。
第二条路径为上图中用蓝色标注的路径,和为 5 + 3 + 0 + 5 + 2 = 15 ,能被 3 整除。

示例 2:

输入:grid = [[0,0]], k = 5
输出:1
解释:红色标注的路径和为 0 + 0 = 0 ,能被 5 整除。

示例 3:

输入:grid = [[7,3,4,9],[2,3,6,2],[2,3,7,0]], k = 1
输出:10
解释:每个数字都能被 1 整除,所以每一条路径的和都能被 k 整除。

提示:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 5 * 10^4
  • 1 <= m * n <= 5 * 10^4
  • 0 <= grid[i][j] <= 100
  • 1 <= k <= 50

解题

方法一:动态规划

思路

找出矩阵中所有(符合条件的)路径,经典的动态规划问题:

  • 状态定义:dp[i][j][x]dp[i][j][x] 表示从 (0,0)(0, 0) 走到 (i,j)(i, j) 时,路径和与 kk 取模正好等于 xx 的路径数量。
  • 状态转移方程:dp[i][j][(x+grid[i][j])modk]=dp[i1][j][x]+dp[i][j1][x]dp[i][j][(x + grid[i][j]) \mod k] = dp[i - 1][j][x] + dp[i][j - 1][x]
  • 初始状态:dp[0][0][grid[0][0]modk]=1dp[0][0][grid[0][0] \mod k] = 1

那么要求的答案:从 (0,0)(0, 0) 走到 (m1,n1)(m - 1, n - 1) 的所有路径和中能被 kk 整除的数量为:dp[m1][n1][0]dp[m - 1][n - 1][0]

注意:

  • 状态转移会从上方和左方同时进行,为例避免下标越界,第一列和第一行要单独处理。
  • 为防止溢出,每次更新答案时都要对 109+710^9+7 进行取模。

代码

class Solution {
    static final int MOD = (int) 1e9 + 7;

    public int numberOfPaths(int[][] grid, int k) {
        int m = grid.length, n = grid[0].length;
        long[][][] dp = new long[m][n][k];
        dp[0][0][grid[0][0] % k] = 1;
        for (int i = 1; i < m; ++i) {
            for (int x = 0; x < k; ++x) dp[i][0][(x + grid[i][0]) % k] = dp[i - 1][0][x] % MOD;
        }
        for (int i = 1; i < n; ++i) {
            for (int x = 0; x < k; ++x) dp[0][i][(x + grid[0][i]) % k] = dp[0][i - 1][x] % MOD;
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                if (i == 0 && j == 0) continue;
                for (int x = 0; x < k; ++x) {
                    dp[i][j][(x + grid[i][j]) % k] = (dp[i - 1][j][x] + dp[i][j - 1][x]) % MOD;
                }
            }
        }
        return (int) dp[m - 1][n - 1][0];
    }
}

把动规数组多开一行一列,下标加一,可以简化代码:

class Solution {
    static final int MOD = (int) 1e9 + 7;

    public int numberOfPaths(int[][] grid, int k) {
        int m = grid.length, n = grid[0].length;
        long[][][] dp = new long[m + 1][n + 1][k];
        dp[1][1][grid[0][0] % k] = 1;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (i == 1 && j == 1) continue;
                for (int x = 0; x < k; ++x) {
                    dp[i][j][(x + grid[i - 1][j - 1]) % k] = (dp[i - 1][j][x] + dp[i][j - 1][x]) % MOD;
                }
            }
        }
        return (int) dp[m][n][0];
    }
}
0

评论区