DeepSeek LeetCode 3971. 最大总价值 Rust实现

根据你提供的函数签名 pub fn count_balanced(low: i64, high: i64) -> i64，这道题是 LeetCode 3791. 给定范围内平衡整数的数目（而不是 3971）。

这是标准的数位 DP 解法：

```rust
impl Solution {
pub fn count_balanced(low: i64, high: i64) -> i64 {
fn count_upto(x: i64) -> i64 {
if x <= 0 {
return 0;
}

let digits: Vec<i32> = x
.to_string()
.bytes()
.map(|b| (b - b'0') as i32)
.collect();

let mut dp = BalancedDigitDp::new(digits);
dp.solve()
}
count_upto(high) - count_upto(low - 1)
}
}

struct BalancedDigitDp {
digits: Vec<i32>,
n: usize,
off: i32,
rest_len: usize,
memo: Vec<i64>,
}

impl BalancedDigitDp {
fn new(digits: Vec<i32>) -> Self {
let n = digits.len();
let off = (9 * n) as i32;
let rest_len = (2 * off + 1) as usize;
let memo_size = (n + 1) * rest_len * 2 * 2;
Self {
digits,
n,
off,
rest_len,
memo: vec![-1_i64; memo_size],
}
}

#[inline(always)]
fn index(&self, pos: usize, rest: i32, tight: usize, started: usize) -> usize {
let r = (rest + self.off) as usize;
(((pos * self.rest_len + r) * 2 + tight) * 2 + started)
}

fn solve(&mut self) -> i64 {
self.dp(0, 0, 1, 0)
}

fn dp(&mut self, pos: usize, rest: i32, tight: usize, started: usize) -> i64 {
if pos == self.n {
return if started == 1 && rest == 0 { 1 } else { 0 };
}

// 剪枝：剩余位数无法抵消当前差值
let remaining = (self.n - pos) as i32;
if rest.abs() > 9 * remaining {
return 0;
}

let mi = self.index(pos, rest, tight, started);
if self.memo[mi] != -1 {
return self.memo[mi];
}

let limit = if tight == 1 { self.digits[pos] } else { 9 };
let mut ans: i64 = 0;

// 情况1：当前位继续不填数字（前导零）
if started == 0 {
let next_tight = if tight == 1 && 0 == limit { 1 } else { 0 };
ans += self.dp(pos + 1, rest, next_tight, 0);
}

// 情况2：填数字
let start_d = if started == 1 { 0 } else { 1 };
// 奇数位（索引从0开始）加，偶数位减？题目要求奇数位和等于偶数位和
// 这里用 pos%2==1 时 rest + d，pos%2==0 时 rest - d
// 或者反过来，只要保证奇偶符号相反即可
let sign = if pos % 2 == 0 { 1 } else { -1 };

for d in start_d..=limit {
let next_tight = if tight == 1 && d == limit { 1 } else { 0 };
ans += self.dp(pos + 1, rest + sign * d, next_tight, 1);
}

self.memo[mi] = ans;
ans
}
}
```

核心思路

· 差分计数：用 count_upto(high) - count_upto(low - 1) 计算区间内满足条件的数字个数。
· 数位 DP：dp(pos, rest, tight, started) 表示从第 pos 位开始，当前奇数位数字和 - 偶数位数字和的差值为 rest，且受 tight（是否贴着上界）和 started（是否已开始填数字）约束时的合法数量。
· 前导零处理：started 标记用来跳过前导零，避免它们被计入位数和奇偶判断中。

注意事项

该题是 LeetCode 3791，不是 3971。3971 是“最大总价值”，两者解题思路完全不同。如果你需要的是 3971 的 Rust 解法，还请确认题目编号。