写在前面
看题解看了半天都看不懂，看了视频也看了好久······，最后还是自己手动模拟才懂的，大佬们写的代码非常好，自己根本想不到该如何用代码实现出来，还是得多刷题，多见一些新题型
题目泉源
这里~~~~~~~QWQ
思绪
考点：DP+三维数组
这里用到三维是因为坐标需要二维来建立，另外每个坐标还需要存储路径的数量，因此必须多开一维
既然是整除的题目，那一定跟取模有很大关系，例如 14 + 4 对 3 取模 14+4对3取模 14+4对3取模 我们可以看成 14 % 3 + 4 % 3 = ( 2 + 1 ) % 3 = 0 14\%3+4\%3=(2+1)\%3=0 14%3+4%3=(2+1)%3=0
起首界说 f [ i ] [ j ] [ v ] 表示从左上走到 ( i , j ) ，且路径和模 k 的效果为 v 时的路径数 f[j][v]表示从左上走到 (i,j)，且路径和模 k 的效果为 v 时的路径数 f[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][0][2]=1,至于f[0][0][0]和f[0][0][1]肯定为0 f[0][0][2]=1,至于f[0][0][0]和f[0][0][1]肯定为0
然后 f [ 0 ] [ 1 ] [ 1 ] = 1 ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ，先看 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[0][1][1]=1······，先看f[1][1]这个点，每个点只跟上边的点和左边的点有关，由于grid[j]=0,那么加上左边和上边的路径和分别为1，2，以是f[1][1][1]=f[1][1][2]=1,背面同理，最后算的是f[m-1][n-1][0],算出最后可以被3整除的路径数量 f[0][1][1]=1⋅⋅⋅⋅⋅⋅，先看f[1][1]这个点，每个点只跟上边的点和左边的点有关，由于grid[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 − g r i d [ i ] [ j ] % k ) % k ] + f [ i ] [ j + 1 ] [ ( v + k − g r i d [ i ] [ j ] % k ) % k ] ) ] % m o d f[i+1][j+1][v]=(f[i+1][j][(v+k-grid[j]\%k)\%k]+f[j+1][(v+k-grid[j]\%k)\%k])]\%mod f[i+1][j+1][v]=(f[i+1][j][(v+k−grid[j]%k)%k]+f[j+1][(v+k−grid[j]%k)%k])]%mod
起首，防止下标越界，让 i 和 j i和j i和j都+1
f [ i + 1 ] [ j + 1 ] [ v ] 为路径和模 k 的效果为 v 时的路径数 f[i+1][j+1][v]为路径和模 k 的效果为 v 时的路径数 f[i+1][j+1][v]为路径和模k的效果为v时的路径数
( v + k − g r i d [ i ] [ j ] % k ) % k 本质上是 v − g r i d [ i ] [ j ] ，即当前 v 的状态由上边以及左边 v − g r i d [ i ] [ j ] 状态而来 (v+k-grid[j]\%k)\%k本质上是v-grid[j]，即当前v的状态由上边以及左边v-grid[j]状态而来 (v+k−grid[j]%k)%k本质上是v−grid[j]，即当前v的状态由上边以及左边v−grid[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];
- }
- };
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
