Kimi LeetCode 3797. 统计在矩形格子里移动的路径数目 Java实现

LeetCode 3797. 统计在矩形格子里移动的路径数目

思路

这题是前缀和优化的动态规划。

状态定义（从下往上递推）：

– `f[i][j]`：从最后一行出发到达 `(i,j)`，且最后一步是从下一行上来的路径数
– `g[i][j]`：从最后一行出发到达 `(i,j)`，且最后一步是同一行横向移动来的路径数

转移：

1. 从下一行上来：从 `(i+1, j')` 到 `(i, j)`，纵向距离为 1，横向距离需满足

   `1 + (j-j')² ≤ d²` → `|j-j'| ≤ ⌊√(d²-1)⌋`。记 `k = ⌊√(d²-1)⌋`。

   `f[i][j] = Σ(f[i+1][j'] + g[i+1][j'])`，其中 `j' ∈ [j-k, j+k]`

2. 同一行横向移动：从 `(i, j')` 到 `(i, j)`，需满足 `|j-j'| ≤ d`，且上一步必须是从下一行上来的（不能连续两次横向）。

   `g[i][j] = Σ(f[i][j'])`，其中 `j' ∈ [j-d, j+d]` 且 `j' ≠ j`

3. 初始化：最后一行每个可用格子作为起点，`f[n-1][j] = 1`

两个转移都是区间求和，用前缀和优化到 `O(1)`，总复杂度 `O(n·m)`。

—

完整 Java 代码

```java
class Solution {
    static final int MOD = 1_000_000_007;

    public int numberOfRoutes(String[] grid, int d) {
        int n = grid.length;
        int m = grid[0].length();
        // 向上移动时，横向最大偏移：sqrt(d^2 – 1)
        int k = (int) Math.sqrt((long) d * d – 1);

        // prefix[i][j][0/1]：第 i 行前 j 个位置（0~j-1）的 f/g 前缀和
        // 同时 prefix[i][j+1][*] = prefix[i][j][*] + dpValue，一物两用
        int[][][] prefix = new int[n][m + 1][2];

        for (int i = n – 1; i >= 0; i–) {
            // 1. 计算 f[i][j]：从下一行上来
            for (int j = 0; j < m; j++) {
                if (grid[i].charAt(j) == '.') {
                    if (i == n – 1) {
                        // 最后一行作为起点
                        prefix[i][j + 1][0] = (prefix[i][j][0] + 1) % MOD;
                    } else {
                        int l = Math.max(j – k, 0);
                        int r = Math.min(j + k, m – 1);
                        int curr = (rangeSum(prefix, i + 1, l, r, 0)
                                  + rangeSum(prefix, i + 1, l, r, 1)) % MOD;
                        prefix[i][j + 1][0] = (prefix[i][j][0] + curr) % MOD;
                    }
                } else {
                    // 阻塞格子，前缀和不变
                    prefix[i][j + 1][0] = prefix[i][j][0];
                }
            }

            // 2. 计算 g[i][j]：同一行横向移动，只能从上一步是"从下一行上来"的状态转移
            for (int j = 0; j < m; j++) {
                if (grid[i].charAt(j) == '.') {
                    int l = Math.max(j – d, 0);
                    int r = Math.min(j + d, m – 1);
                    // 排除 j 本身（j' != j），拆成 [l, j-1] 和 [j+1, r] 两段
                    int left  = rangeSum(prefix, i, l, j – 1, 0);
                    int right = rangeSum(prefix, i, j + 1, r, 0);
                    int curr = (left + right) % MOD;
                    prefix[i][j + 1][1] = (prefix[i][j][1] + curr) % MOD;
                } else {
                    prefix[i][j + 1][1] = prefix[i][j][1];
                }
            }
        }

        // 第 0 行所有可用格子的 f + g 之和
        return (prefix[0][m][0] + prefix[0][m][1]) % MOD;
    }

    // 用前缀和数组求第 row 行 [l, r] 区间内某状态的和
    private int rangeSum(int[][][] prefix, int row, int l, int r, int state) {
        if (l > r) return 0;
        return (prefix[row][r + 1][state] – prefix[row][l][state] + MOD) % MOD;
    }
}
```

—

复杂度

项目    复杂度    
时间    `O(n × m)`    
空间    `O(n × m)`（可优化到 `O(m)`，只需保留相邻两行）