【三维DP的简单应用】-创新互联

LeetCode 2435. 矩阵中和能被 K 整除的路径 算法：动态规划

设 f ( i , j , t ) f(i, j, t) f(i,j,t) 表示当前在的格子坐标为 ( i , j ) (i, j) (i,j)，且所有到达此点的路径和（包括此点）对 k k k 取余数为 t t t 的方案数。

绿园网站制作公司哪家好，找创新互联公司！从网页设计、网站建设、微信开发、APP开发、响应式网站等网站项目制作，到程序开发，运营维护。创新互联公司于2013年创立到现在10年的时间，我们拥有了丰富的建站经验和运维经验，来保证我们的工作的顺利进行。专注于网站建设就选创新互联公司。

由于只能往下和往右走，因此可以得到状态转移方程：

f ( i , j , ( g [ i ] [ j ] + t ) % k ) = f ( i − 1 , j , t ) + f ( i , j − 1 , t ) f(i, j, (g[i][j] + t) \% k) = f(i - 1, j, t) + f(i, j - 1, t) f(i,j,(g[i][j]+t)%k)=f(i−1,j,t)+f(i,j−1,t)

所以只需要三重循环，前两重枚举坐标，最内层枚举余数，从0 ~ k - 1即可

时间复杂度 O ( n m k ) O(nmk) O(nmk) C++ 代码

typedef long long LL;

const int MOD = 1e9 + 7;

class Solution {public:
    int numberOfPaths(vector>& g, int k) {int n = g.size(), m = g[0].size();

        vector>>f(n, vector>(m, vector(k)));
        f[0][0][g[0][0] % k] = 1;

        for (int i = 0; i< n; i ++ )
            for (int j = 0; j< m; j ++ ) {if (i) {for (int t = 0; t< k; t ++ ) {auto &x = f[i][j][(g[i][j] + t) % k];
                        x = ((LL)x + f[i - 1][j][t]) % MOD;
                    }
                }
                if (j) {for (int t = 0; t< k; t ++ ) {auto &x = f[i][j][(g[i][j] + t) % k];
                        x = ((LL)x + f[i][j - 1][t]) % MOD;
                    }
                }
            }

        return f[n - 1][m - 1][0];
    }
};

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

网页名称：【三维DP的简单应用】-创新互联
分享路径：http://cqcxhl.cn/article/deeocs.html