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

LeetCode 3797. 统计在矩形格子里移动的路径数目 — TypeScript 实现思路状态定义从下往上递推- f[i][j]到达 (i, j)且最后一步是从下一行纵向移动上来的路径数- g[i][j]到达 (i, j)且最后一步是同一行横向移动来的路径数转移方程1. 纵向移动从 (i1, j) 到 (i, j)要求 √(1 (j-j)²) ≤ d即 |j-j| ≤ √(d²-1)。记 k ⌊√(d²-1)⌋。f[i][j] Σ(f[i1][j] g[i1][j])j ∈ [j-k, jk]2. 横向移动从 (i, j) 到 (i, j)要求 |j-j| ≤ d 且 j ≠ j。关键限制不能连续两次横向移动所以横向移动的前一步必须是从下一行上来的。g[i][j] Σ(f[i][j])j ∈ [j-d, jd] 且 j ≠ j3. 初始化最后一行每个空地作为起点f[n-1][j] 1两个转移都是区间求和用前缀和优化到 O(1)总复杂度 O(n·m)。---TypeScript 代码typescriptfunction numberOfRoutes(grid: string[], d: number): number {const MOD 1_000_000_007;const n grid.length;const m grid[0].length;// 纵向移动时横向最大偏移floor(sqrt(d^2 - 1))const k Math.floor(Math.sqrt(d * d - 1));// prefix[i][j][0]: 第 i 行前 j 个位置0~j-1的 f 之和// prefix[i][j][1]: 第 i 行前 j 个位置0~j-1的 g 之和const prefix: number[][][] Array.from({ length: n }, () Array.from({ length: m 1 }, () [0, 0]));const add (a: number, b: number): number (a b) % MOD;const sub (a: number, b: number): number (a - b MOD) % MOD;for (let i n - 1; i 0; i--) {// 1. 计算 f[i][j]从下一行上来for (let j 0; j m; j) {if (grid[i][j] .) {if (i n - 1) {// 最后一行作为起点prefix[i][j 1][0] add(prefix[i][j][0], 1);} else {const l Math.max(j - k, 0);const r Math.min(j k, m - 1);const sumF sub(prefix[i 1][r 1][0], prefix[i 1][l][0]);const sumG sub(prefix[i 1][r 1][1], prefix[i 1][l][1]);const curr add(sumF, sumG);prefix[i][j 1][0] add(prefix[i][j][0], curr);}} else {// 障碍物前缀和不变prefix[i][j 1][0] prefix[i][j][0];}}// 2. 计算 g[i][j]同一行横向移动// 只能从上一步是从下一行上来的状态转移不能连续横向for (let j 0; j m; j) {if (grid[i][j] .) {const l Math.max(j - d, 0);const r Math.min(j d, m - 1);// 排除 j 本身拆成 [l, j-1] 和 [j1, r] 两段let left 0, right 0;if (l j - 1) {left sub(prefix[i][j][0], prefix[i][l][0]);}if (j 1 r) {right sub(prefix[i][r 1][0], prefix[i][j 1][0]);}const curr add(left, right);prefix[i][j 1][1] add(prefix[i][j][1], curr);} else {prefix[i][j 1][1] prefix[i][j][1];}}}// 第 0 行所有可用格子的 f g 之和return add(prefix[0][m][0], prefix[0][m][1]);}---复杂度项目 复杂度时间 O(n × m)空间 O(n × m)可滚动优化至 O(m)