以下是 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)。