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

题目如下

数据范围

本题同样是由于一个坐标对应的状态数不唯一所以需要三维数组来存储状态并转移。
显然我们无需关心具体的数只需要计算余数即可（（a + b）% k == a % k + b % k）
所以我们用余数的可能取值(0 到 k - 1)作为状态。

通过代码

class Solution {
public:
    int numberOfPaths(vector<vector<int>>& grid, int k) {
        int mod = 1e9 + 7;
        int n = grid.size();
        int m = grid[0].size();
        int t;
        vector<vector<vector<int>>> dp(k,vector<vector<int>>(n,vector<int>(m,0)));
        dp[grid[0][0] % k][0][0] = 1;
        for(int i = 1;i < m;i++){
            t = grid[0][i] % k;
            for(int j = 0;j < k;j++){
                   dp[(t + j) % k][0][i] = dp[j][0][i - 1];
            }
        }
        for(int i = 1;i < n;i++){
            t = grid[i][0] % k;
             for(int j = 0;j < k;j++){
                   dp[(t + j) % k][i][0] = dp[j][i - 1][0];
            }
        }
        for(int i = 1;i < n;i++){
            for(int j = 1;j < m;j++){
                t = grid[i][j] % k;
                for(int l = 0;l < k;l++){
                    dp[(t + l) % k][i][j] = dp[l][i - 1][j];
                    dp[(t + l) % k][i][j] = (dp[(t + l) % k][i][j] + dp[l][i][j - 1]) % mod;
                    
                }
            }
        }
        return dp[0][n - 1][m - 1] % mod;
    }
};