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

以下是 LeetCode 3906 的 Rust 实现，采用数位 DP 思路，核心是将路径上访问的 7 个格子标记为关键位，然后对 `[0, x]` 范围内的数进行记忆化搜索。

```rust
impl Solution {
pub fn count_good_integers_on_path(l: i64, r: i64, directions: String) -> i64 {
// 标记路径上访问的 7 个关键格子（行优先顺序：pos = row * 4 + col）
let mut key = [false; 16];
let (mut row, mut col) = (0, 0);
key[0] = true; // 起点 (0,0)
for c in directions.chars() {
if c == 'D' {
row += 1;
} else {
col += 1;
}
key[row * 4 + col] = true;
}

// 数位 DP：计算 [0, x] 中满足条件的数的个数
let mut calc = |x: i64| -> i64 {
if x < 0 {
return 0;
}
// 将 x 补齐为 16 位字符串
let s = format!("{:016}", x);
let s_bytes = s.as_bytes();

// 记忆化数组 f[pos][last]，-1 表示未计算
let mut f = [[-1i64; 10]; 16];

fn dfs(
pos: usize,
last: usize,
lim: bool,
key: &[bool; 16],
s_bytes: &[u8],
f: &mut [[i64; 10]; 16],
) -> i64 {
if pos == 16 {
return 1;
}
// 非受限状态且已计算过，直接返回
if !lim && f[pos][last] != -1 {
return f[pos][last];
}

let mut res = 0i64;
// 当前位的下界：如果是关键位，必须 >= last；否则可以从 0 开始
let start = if key[pos] { last } else { 0 };
// 当前位的上界：如果受限，则为 s[pos]；否则为 9
let end = if lim {
(s_bytes[pos] - b'0') as usize
} else {
9
};

for i in start..=end {
let next_last = if key[pos] { i } else { last };
let next_lim = lim && (i == end);
res += dfs(pos + 1, next_last, next_lim, key, s_bytes, f);
}

// 只有非受限状态才缓存结果
if !lim {
f[pos][last] = res;
}
res
}

dfs(0, 0, true, &key, s_bytes, &mut f)
};

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~9`，`last` 保持不变。

3. 受限状态 `lim`：表示当前位是否被上界 `s[pos]` 限制。如果受限，当前位最大只能填 `s[pos]`；否则可以填到 `9`。只有非受限状态的结果可以缓存。

4. 区间转换：通过 `calc(r) - calc(l - 1)` 得到 `[l, r]` 范围内的答案。

时间复杂度 O(16 \times 10 \times 10)，空间复杂度 O(16 \times 10)，完全在可接受范围内。