Kimi LeetCode 3906. 统计网格路径中好整数的数目 C语言实现-北京尧图网络

以下是 LeetCode 3906 的 C 语言实现采用数位 DP 思路。由于 C 没有内置的递归记忆化使用静态数组手动实现记忆化搜索。c#include stdio.h#include stdlib.h#include string.h// 全局/静态变量用于 DFSstatic bool key[16];static long long memo[16][10];static char s[17]; // 16位数字 \0static long long dfs(int pos, int last, bool lim) {if (pos 16) {return 1;}// 非受限状态且已计算过直接返回if (!lim memo[pos][last] ! -1) {return memo[pos][last];}long long res 0;// 当前位的下界如果是关键位必须 last否则从 0 开始int start key[pos] ? last : 0;// 当前位的上界如果受限则为 s[pos]否则为 9int end lim ? (s[pos] - 0) : 9;for (int i start; i end; i) {int next_last key[pos] ? i : last;bool next_lim lim (i end);res dfs(pos 1, next_last, next_lim);}// 只有非受限状态才缓存结果if (!lim) {memo[pos][last] res;}return res;}static long long calc(long long x) {if (x 0) {return 0;}// 将 x 补齐为 16 位字符串snprintf(s, sizeof(s), %016lld, x);// 初始化记忆化数组为 -1for (int i 0; i 16; i) {for (int j 0; j 10; j) {memo[i][j] -1;}}return dfs(0, 0, true);}long long countGoodIntegersOnPath(long long l, long long r, char* directions) {// 标记路径上访问的 7 个关键格子memset(key, 0, sizeof(key));int row 0, col 0;key[0] true; // 起点 (0,0)for (int i 0; directions[i] ! \0; i) {if (directions[i] D) {row;} else {col;}key[row * 4 col] true;}return calc(r) - calc(l - 1);}关键思路说明1. 路径预处理directions 恰好包含 3 个 D 和 3 个 R从 (0,0) 出发走 6 步到达 (3,3)。将路径上经过的 7 个格子在 16 位字符串中的位置row * 4 col标记为 key[pos] true。2. 数位 DP将数字补齐为 16 位后逐位枚举。对于每个位置 pos- 如果 key[pos] true路径上的格子当前位必须 ≥ 上一个路径格子的值last同时更新 last。- 如果 key[pos] false非路径上的格子可以填任意数字 0~9last 保持不变。3. 受限状态 lim表示当前位是否被上界 s[pos] 限制。如果受限当前位最大只能填 s[pos]否则可以填到 9。只有非受限状态的结果可以缓存到 memo 数组中。4. 区间转换通过 calc(r) - calc(l - 1) 得到 [l, r] 范围内的答案。时间复杂度 O(16 \times 10 \times 10)空间复杂度 O(16 \times 10)。

Kimi LeetCode 3906. 统计网格路径中好整数的数目 C语言实现

相关推荐

GB/T 12459-2025 新国标完整技术解读｜替代 2017 版，管道工程师必看

Lottie、Rive 与 CustomPainter，要按交互路径选

从 /IWPGW/TASKPROCESSING 到 TaskCollection，彻底搞懂 SAP Task Gateway Service 的激活过程

更多资讯

1024 特刊｜用稀疏自编码器拆开激活：重构得好，为什么仍不能直接叫“找到知识”

1024 特刊｜机器人先想再动：把高层推理、坐标变换和闭环控制分开

1024 特刊｜从 A* 到 MCTS：过程奖励分数为什么不能直接当最短路启发函数

LLM面试必问的8个核心问题：从Transformer到微调的深度解析

LLM面试8大核心问题：Transformer、Tokenization、Embedding与Function Calling底层原理

生产级Agent内核设计：14个关键决策与四大复利引擎

今日更新

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本周精选

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

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