golang 解法, 执行用时: 188 ms, 内存消耗: 53.2 MB, 提交时间: 2023-08-16 17:23:18

func numberOfPaths(grid [][]int, k int) int {
	const mod int = 1e9 + 7
	m, n := len(grid), len(grid[0])
	f := make([][][]int, m+1)
	for i := range f {
		f[i] = make([][]int, n+1)
		for j := range f[i] {
			f[i][j] = make([]int, k)
		}
	}
	f[0][1][0] = 1
	for i, row := range grid {
		for j, x := range row {
			for v := 0; v < k; v++ {
				f[i+1][j+1][(v+x)%k] = (f[i+1][j][v] + f[i][j+1][v]) % mod
			}
		}
	}
	return f[m][n][0]
}

cpp 解法, 执行用时: 200 ms, 内存消耗: 52.4 MB, 提交时间: 2023-08-16 17:22:59

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

java 解法, 执行用时: 49 ms, 内存消耗: 79.1 MB, 提交时间: 2023-08-16 17:22:39

class Solution {
    public int numberOfPaths(int[][] grid, int k) {
        final var mod = (int) 1e9 + 7;
        int m = grid.length, n = grid[0].length;
        var f = new int[m + 1][n + 1][k];
        f[0][1][0] = 1;
        for (var i = 0; i < m; ++i)
            for (var j = 0; j < n; ++j)
                for (var v = 0; v < k; ++v)
                    f[i + 1][j + 1][(v + grid[i][j]) % k] = (f[i + 1][j][v] + f[i][j + 1][v]) % mod;
        return f[m][n][0];
    }
}

python3 解法, 执行用时: 2364 ms, 内存消耗: 94.7 MB, 提交时间: 2023-08-16 17:21:57

'''
套路：把路径和模 k 的结果当成一个扩展维度。
具体地，定义 f[i][j][v] 表示从左上走到 (i,j)，且路径和模 k 的结果为 v 时的路径数。
初始值 f[0][0][grid[0][0] % k]=1，答案为 f[m−1][n−1][0]。

考虑从左边和上边转移过来，则有f[i][j][(v+grid[i][j]) % k]=f[i][j−1][v]+f[i−1][j][v]
'''
class Solution:
    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:
        MOD = 10 ** 9 + 7
        m, n = len(grid), len(grid[0])
        f = [[[0] * k for _ in range(n + 1)] for _ in range(m + 1)]
        f[0][1][0] = 1
        for i, row in enumerate(grid):
            for j, x in enumerate(row):
                for v in range(k):
                    f[i + 1][j + 1][(v + x) % k] = (f[i + 1][j][v] + f[i][j + 1][v]) % MOD
        return f[m][n][0]