Leetcode每日一题：矩阵中和能被 K 整除的路径

Leetcode每日一题 —— 2435. 矩阵中和能被 K 整除的路径

思路
由左、上的状态即可算出当前格子求余结果的数量，因此是典型的递推/动态规划题目。
转移方程：f(x,y,t)=f(x-1,y,t-mod)+f(x,y-1,t-mod)，其中t代表余数值，t-mod用(t + k - mod) % k来计算

代码

public int numberOfPaths(int grid, int k) {
    int m = grid.length;
    int n = grid[0].length;
    int dp = new int[m][n][k];
    int tmp = grid[0][0];
    dp[0][0][tmp % k] = 1;
    for (int i = 1; i < m; i++) {
        tmp += grid[i][0];
        dp[i][0][tmp % k] = 1;
    }
    tmp = grid[0][0];
    for (int i = 1; i < n; i++) {
        tmp += grid[0][i];
        dp[0][i][tmp % k] = 1;
    }
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            int mod = grid[i][j] % k;
            for (int t = 0; t < k; t++) {
                dp[i][j][t] = (dp[i - 1][j][(t + k - mod) % k] + dp[i][j - 1][(t + k - mod) % k]) % 1000000007;
            }
        }
    }
    return dp[m - 1][n - 1][0];
}

时间复杂度：O(mnk)
空间复杂度：O(mnk)

4 posts - 3

via - (author: 魔法师)