以下是 LeetCode 3704「统计和为 N 的无零数对」的 Java 实现。思路数位 DP由于 n 最大可达 10^15枚举所有数对会超时需要用 数位 DP 来解决。核心思想是从 最低位到最高位 逐位处理 n 的十进制表示状态定义为- dp[carry][aliveA][aliveB]处理到当前位时低位进位为 carrya 和 b 是否还在更高位有有效数字aliveA/aliveB。转移时枚举当前位 da 和 db- 如果 aliveX 1当前位可以取 1~9无零或在非最低位时取 0表示该数到此结束。- 如果 aliveX 0当前位只能取 0前导零不属于十进制表示。需要满足 (da db carry) % 10 n 的当前位。最后给 n 补一位 0 来吸收最终进位答案为 dp[0][0][0]。时间复杂度 O(L × 9²)空间复杂度 O(1)其中 L 为 n 的位数。javaclass Solution {public long countNoZeroPairs(long n) {char[] cs Long.toString(n).toCharArray();int m cs.length;// digits[i] 表示 n 的第 i 位从低位到高位0-basedint[] digits new int[m 1];for (int i 0; i m; i) {digits[i] cs[m - 1 - i] - 0;}digits[m] 0; // 额外补一位最高位 0吸收最终进位// dp[carry][aliveA][aliveB]long[][][] dp new long[2][2][2];dp[0][1][1] 1; // 初始状态无进位a 和 b 都还在存活for (int pos 0; pos m 1; pos) {long[][][] ndp new long[2][2][2];int target digits[pos];for (int carry 0; carry 1; carry) {for (int aliveA 0; aliveA 1; aliveA) {for (int aliveB 0; aliveB 1; aliveB) {long ways dp[carry][aliveA][aliveB];if (ways 0) {continue;}// 构造 a 当前位可选的数字及对应的 aliveA 下一状态int[] aDigits;int[] aNext;if (aliveA 1) {if (pos 0) {// 最低位必须是非零数字1~9因为 a 是正整数aDigits new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9};aNext new int[] {1, 1, 1, 1, 1, 1, 1, 1, 1};} else {// 非最低位可以选 1~9继续存活或选 0在此结束aDigits new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};aNext new int[] {1, 1, 1, 1, 1, 1, 1, 1, 1, 0};}} else {// a 已经结束当前位只能是 0aDigits new int[] {0};aNext new int[] {0};}// 构造 b 当前位可选的数字及对应的 aliveB 下一状态int[] bDigits;int[] bNext;if (aliveB 1) {if (pos 0) {bDigits new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9};bNext new int[] {1, 1, 1, 1, 1, 1, 1, 1, 1};} else {bDigits new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};bNext new int[] {1, 1, 1, 1, 1, 1, 1, 1, 1, 0};}} else {bDigits new int[] {0};bNext new int[] {0};}for (int ai 0; ai aDigits.length; ai) {int da aDigits[ai];int na aNext[ai];for (int bi 0; bi bDigits.length; bi) {int db bDigits[bi];int nb bNext[bi];int s da db carry;if (s % 10 ! target) {continue;}int ncarry s / 10;ndp[ncarry][na][nb] ways;}}}}}dp ndp;}// 最终要求无剩余进位a 和 b 都已经结束return dp[0][0][0];}}关键点说明1. 从低位到高位处理因为加法进位是从低位向高位传递的。2. alive 状态表示该数在更高位是否还有有效数字。alive 0 意味着该数已经结束更高位只能填 0前导零不计入十进制表示。3. 最低位特殊处理pos 0 时a 和 b 的最低位不能取 0因为它们是正整数最低位必须是 1~9。4. 额外补位digits[m] 0 用于处理最高位可能产生的进位确保所有状态正确收敛。