非常套路的动态规划。因为最终我们要求路径和恰好是k的倍数，所以在每个中途的点，我们必须考虑当前路径和对k的余数状态。因此我们定义dp[i][j][r]表示从起点到(i,j)有多少条不同路径使得沿途的元素和对k的取模是r。根据套路，dp[i][j][r] = dp[i-1][j][t] + dp[i][j-1][t]，其中t必须满足(t + grid[i][j]) % k = r.
最终返回dp[m-1][n-1][0].
2435.Paths-in-Matrix-Whose-Sum-Is-Divisible-by-K
Folders and files
| Name | Name | Last commit date | ||
|---|---|---|---|---|
parent directory.. | ||||