以下是 LeetCode 3704「统计和为 N 的无零数对」的 Rust 实现。思路数位 DP与 Java 实现相同从 最低位到最高位 逐位处理 n 的十进制表示。状态 dp[carry][aliveA][aliveB] 表示处理到当前位时低位进位为 carrya 和 b 是否还在更高位有有效数字。rustimpl Solution {pub fn count_no_zero_pairs(n: i64) - i64 {let s n.to_string();let m s.len();// digits[i] 表示 n 的第 i 位从低位到高位0-basedlet mut digits vec![0; m 1];for (i, c) in s.chars().rev().enumerate() {digits[i] (c as u8 - b0) as usize;}// digits[m] 已经是 0用于吸收最终进位// dp[carry][aliveA][aliveB]let mut dp [[[0i64; 2]; 2]; 2];dp[0][1][1] 1;for pos in 0..m {let mut ndp [[[0i64; 2]; 2]; 2];let target digits[pos];for carry in 0..1 {for alive_a in 0..1 {for alive_b in 0..1 {let ways dp[carry][alive_a][alive_b];if ways 0 {continue;}// 构造 a 当前位可选的数字及对应的下一 alive 状态let a_choices: Vec(usize, usize) if alive_a 1 {if pos 0 {// 最低位必须是非零数字(1..9).map(|d| (d, 1)).collect()} else {// 非最低位可以选 1~9 继续或选 0 结束let mut v: Vec(usize, usize) (1..9).map(|d| (d, 1)).collect();v.push((0, 0));v}} else {vec![(0, 0)]};// 构造 b 当前位可选的数字及对应的下一 alive 状态let b_choices: Vec(usize, usize) if alive_b 1 {if pos 0 {(1..9).map(|d| (d, 1)).collect()} else {let mut v: Vec(usize, usize) (1..9).map(|d| (d, 1)).collect();v.push((0, 0));v}} else {vec![(0, 0)]};for (da, na) in a_choices {for (db, nb) in b_choices {let sum da db carry;if sum % 10 ! target {continue;}let ncarry sum / 10;ndp[ncarry][na][nb] ways;}}}}}dp ndp;}dp[0][0][0]}}关键点说明要点 说明从低位到高位 加法进位天然从低位向高位传递数位 DP 必须按此顺序alive 状态 alive 1 表示该数在更高位还有有效数字alive 0 表示已结束后续只能填 0最低位限制 pos 0 时a 和 b 的最低位不能取 0因为它们是正整数非最低位可选 0 当 pos 0 时选 0 表示该数在此位结束alive 变为 0额外补位 digits[m] 0 用于处理最高位可能产生的进位确保状态正确收敛时间复杂度 O(L × 9²)空间复杂度 O(1)其中 L 为 n 的位数最多 16 位。