下面是 LeetCode 3869. 统计区间内奇妙数的数目 的 Rust 实现。

解题思路

这道题使用数位 DP（Digit DP）来解决。核心思路：

1. 好数：数位严格递增或严格递减的数（一位数默认是好数）
2. 奇妙数：本身是好数，或者其数位和是好数
3. 用 `calc(r) - calc(l-1)` 计算区间 `[l, r]` 内的答案

数位 DP 状态：`dfs(pos, sum, prev, st, lim)`
- `pos`：当前处理到的数位位置
- `sum`：当前数位和（最大 `16×9=144`）
- `prev`：前一个数位的值
- `st`：单调状态（`0`=初始/前导零, `1`=递增, `2`=递减, `3`=非单调）
- `lim`：是否受上界限制

check 函数优化：由于数位和最大只有 144，判断好数时可以优化：
- `s < 100`：不是 11 的倍数即为好数（因为两位数中 `11, 22, ..., 99` 不是好数）
- `s ≥ 100`：只需检查十位和个位是否满足 `1 < mid < last`

Rust 代码

```rust
impl Solution {
    pub fn count_fancy(l: i64, r: i64) -> i64 {
        Self::calc(r) - Self::calc(l - 1)
    }

    fn calc(x: i64) -> i64 {
        if x < 0 {
            return 0;
        }
        let num = x.to_string();
        let n = num.len();
        // dp[pos][sum][prev][state], -1 表示未计算
        // state: 0=初始(前导零), 1=递增, 2=递减, 3=非单调
        let mut dp = vec![vec![vec![vec![-1i64; 4]; 10]; 9 * n + 1]; n];
        Self::dfs(0, 0, 0, 0, true, &num, n, &mut dp)
    }

    fn dfs(
        pos: usize,
        sum: usize,
        prev: usize,
        st: usize,
        lim: bool,
        num: &str,
        n: usize,
        dp: &mut Vec<Vec<Vec<Vec<i64>>>>,
    ) -> i64 {
        if pos >= n {
            // 如果本身是好数，直接计数
            if st != 3 {
                return 1;
            }
            // 否则检查数位和是否是好数
            return if Self::check(sum) { 1 } else { 0 };
        }

        // 记忆化搜索（不受限状态时）
        if !lim && dp[pos][sum][prev][st] != -1 {
            return dp[pos][sum][prev][st];
        }

        let up = if lim {
            (num.as_bytes()[pos] - b'0') as usize
        } else {
            9
        };

        let mut res: i64 = 0;
        for i in 0..=up {
            // 更新单调状态
            let nxt_st = if st == 0 {
                if prev == 0 {
                    0 // 前导零或第一个数字
                } else if i > prev {
                    1 // 开始递增
                } else if i < prev {
                    2 // 开始递减
                } else {
                    3 // 相等，非单调
                }
            } else if st == 1 {
                if i > prev { 1 } else { 3 }
            } else if st == 2 {
                if i < prev { 2 } else { 3 }
            } else {
                3
            };

            // 更新前一个数位（保持前导零状态）
            let nxt_prev = if st == 0 && prev == 0 && i == 0 {
                0
            } else {
                i
            };

            res += Self::dfs(
                pos + 1,
                sum + i,
                nxt_prev,
                nxt_st,
                lim && i == up,
                num,
                n,
                dp,
            );
        }

        if !lim {
            dp[pos][sum][prev][st] = res;
        }

        res
    }

    // 判断 s 是否是好数（s 为数位和，最大 144）
    fn check(s: usize) -> bool {
        if s < 100 {
            return s % 11 != 0;
        }
        let mid = (s / 10) % 10;
        let last = s % 10;
        mid > 1 && mid < last
    }
}
```

复杂度分析

- 时间复杂度：`O(D³ × log r)`，其中 `D = 10` 为数字范围，状态数为 `pos × sum × prev × st ≈ 16 × 145 × 10 × 4`
- 空间复杂度：`O(D² × log r)`，记忆化数组的大小