百度提交入口网站怎么看_莱芜在线论坛莱芜话题秦立奉_中国市场营销网网站_网络公司网络营销推广方案

题目如下

数据范围

本题同样是由于一个坐标对应的状态数不唯一所以需要三维数组来存储状态并转移。
显然我们无需关心具体的数只需要计算余数即可（（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;}
};