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

标题如下

数据范围

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

复制代码

通过代码

1. class Solution {
2. public:
3.     int numberOfPaths(vector<vector<int>>& grid, int k) {
4.         int mod = 1e9 + 7;
5.         int n = grid.size();
6.         int m = grid[0].size();
7.         int t;
8.         vector<vector<vector<int>>> dp(k,vector<vector<int>>(n,vector<int>(m,0)));
9.         dp[grid[0][0] % k][0][0] = 1;
10.         for(int i = 1;i < m;i++){
11.             t = grid[0][i] % k;
12.             for(int j = 0;j < k;j++){
13.                    dp[(t + j) % k][0][i] = dp[j][0][i - 1];
14.             }
15.         }
16.         for(int i = 1;i < n;i++){
17.             t = grid[i][0] % k;
18.              for(int j = 0;j < k;j++){
19.                    dp[(t + j) % k][i][0] = dp[j][i - 1][0];
20.             }
21.         }
22.         for(int i = 1;i < n;i++){
23.             for(int j = 1;j < m;j++){
24.                 t = grid[i][j] % k;
25.                 for(int l = 0;l < k;l++){
26.                     dp[(t + l) % k][i][j] = dp[l][i - 1][j];
27.                     dp[(t + l) % k][i][j] = (dp[(t + l) % k][i][j] + dp[l][i][j - 1]) % mod;
28.                     
29.                 }
30.             }
31.         }
32.         return dp[0][n - 1][m - 1] % mod;
33.     }
34. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。