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)

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

相关推荐

Linux系统下阿里云盘命令行与FUSE挂载实战指南

Unity游戏实时翻译实战：基于BepInEx与XUnity.AutoTranslator的完整指南

OpenClaw-RL：大模型规划与强化学习协同的智能体自主进化框架

更多资讯

Atlas 300V 24G是运算加速卡吗？从NPU到YOLO部署全解读

TCP/IP协议首部解析：网络通信的底层指令集与故障排查指南

从零自研CRM系统：Spring Boot+Vue实战技术解析

Windows 10远程桌面全链路排错指南：从NLA校验到会话资源管理

2026年深圳南山知名的冯校长老火锅，宝安性价比高的火锅店本地靠谱服务机构排行榜

Phoenix 中 OTel contextvars 与 async 边界的实战避坑指南：为何不在异步生成器清理路径里使用 contextvars

今日更新

AI元人文：从工具使用到思维重构的深度探索

Python+CNN车牌识别实战：从数据预处理到模型训练与部署

Vim基础操作全攻略：保存退出、模式切换与高频命令实战

本周精选

深入解析Transformer多头注意力机制与工程优化

OpenClaw 的 Skills 跑学习任务，模型通道改到 TaoToken 通道行不行？

ChatGPT报错Oops, an error occurred! 全链路排查指南

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？