当前位置：首页 > news >正文

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

news 来源：原创 2024/9/16 10:30:15

文章目录

写在前面
题目来源
思路
code

写在前面

看题解看了半天都看不懂，看了视频也看了好久······，最后还是自己手动模拟才懂的，大佬们写的代码非常好，自己根本想不到该如何用代码实现出来，还是得多刷题，多见一些新题型

题目来源

这里~~~~~~~QWQ

思路

考点：DP+三维数组
这里用到三维是因为坐标需要二维来建立，另外每个坐标还需要存储路径的数量，因此必须多开一维
既然是整除的题目，那必然跟取模有很大关系，例如 $14 + 4 对 3 取模$ 我们可以看成 $14\%3+4\%3=(2+1)\%3=0$
首先定义 $f [i] [j] [v] 表示从左上走到 (i, j) ，且路径和模 k 的结果为 v 时的路径数$
先看样例：(k=3)

那么路径和取模3为：

2 1 2
2 (2,1) (0,1,1)
2 (0,0,2) (0,0,1,2,2,2)
首先先定义边界， $f [0] [0] [2] = 1, 至于 f [0] [0] [0] 和 f [0] [0] [1] 肯定为 0$
然后 $f [0] [1] [1] = 1 \cdot\cdot\cdot\cdot\cdot\cdot ，先看 f [1] [1] 这个点，每个点只跟上边的点和左边的点有关，由于 g r i d [i] [j] = 0, 那么加上左边和上边的路径和分别为 1 ， 2 ，所以 f [1] [1] [1] = f [1] [1] [2] = 1, 后面同理，最后算的是 f [m - 1] [n - 1] [0], 算出最后可以被 3 整除的路径数量$

模拟如此，代码如何实现呢？

参考模拟，状态转移方程就为：
$f[i+1][j+1][v]=(f[i+1][j][(v+k-grid[i][j]\%k)\%k]+f[i][j+1][(v+k-grid[i][j]\%k)\%k])]\%mod$
首先，防止下标越界，让 $i 和 j$ 都+1
$f [i + 1] [j + 1] [v] 为路径和模 k 的结果为 v 时的路径数$
$(v+k-grid[i][j]\%k)\%k本质上是v-grid[i][j]，即当前v的状态由上边以及左边v-grid[i][j]状态而来$
至于取模k的操作就是防止下标越界

接下来看代码

code

class Solution {
public:int numberOfPaths(vector<vector<int>>& grid, int k) {int m=grid.size(),n=grid[0].size();int mod=1e9+7;int f[m+1][n+1][k];memset(f,0,sizeof f);f[1][0][0]=1;//初始化for(int i=0;i<m;++i)for(int j=0;j<n;++j)for(int v=0;v<k;++v){f[i+1][j+1][v]=(f[i+1][j][(v+k-grid[i][j]%k)%k]+f[i][j+1][(v+k-grid[i][j]%k)%k])%mod;}return f[m][n][0];}
};