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

根据你提供的函数签名 pub fn count_balanced(low: i64, high: i64) - i64这道题是 LeetCode 3791. 给定范围内平衡整数的数目而不是 3971。这是标准的数位 DP 解法rustimpl Solution {pub fn count_balanced(low: i64, high: i64) - i64 {fn count_upto(x: i64) - i64 {if x 0 {return 0;}let digits: Veci32 x.to_string().bytes().map(|b| (b - b0) as i32).collect();let mut dp BalancedDigitDp::new(digits);dp.solve()}count_upto(high) - count_upto(low - 1)}}struct BalancedDigitDp {digits: Veci32,n: usize,off: i32,rest_len: usize,memo: Veci64,}impl BalancedDigitDp {fn new(digits: Veci32) - 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%21 时 rest dpos%20 时 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) 计算区间内满足条件的数字个数。· 数位 DPdp(pos, rest, tight, started) 表示从第 pos 位开始当前奇数位数字和 - 偶数位数字和的差值为 rest且受 tight是否贴着上界和 started是否已开始填数字约束时的合法数量。· 前导零处理started 标记用来跳过前导零避免它们被计入位数和奇偶判断中。注意事项该题是 LeetCode 3791不是 3971。3971 是“最大总价值”两者解题思路完全不同。如果你需要的是 3971 的 Rust 解法还请确认题目编号。