企业官网建设流程全解析

以下是 LeetCode 3704「统计和为 N 的无零数对」的 Rust 实现。

思路：数位 DP

与 Java 实现相同，从 最低位到最高位 逐位处理 `n` 的十进制表示。状态 `dp[carry][aliveA][aliveB]` 表示处理到当前位时，低位进位为 `carry`，`a` 和 `b` 是否还在更高位有有效数字。

```rust
impl Solution {
pub fn count_no_zero_pairs(n: i64) -> i64 {
let s = n.to_string();
let m = s.len();
// digits[i] 表示 n 的第 i 位（从低位到高位，0-based）
let mut digits = vec![0; m + 1];
for (i, c) in s.chars().rev().enumerate() {
digits[i] = (c as u8 - b'0') 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 位）。