Kimi LeetCode 3704. 统计和为 N 的无零数对 JavaScript实现

以下是 LeetCode 3704「统计和为 N 的无零数对」的 JavaScript 实现。思路数位 DP从 最低位到最高位 逐位处理 n 的十进制表示。状态 dp[carry][aliveA][aliveB] 表示处理到当前位时低位进位为 carrya 和 b 是否还在更高位有有效数字。javascript/*** param {number} n* return {number}*/var countNoZeroPairs function(n) {// 将 n 转为从低位到高位的数字数组const s n.toString();const m s.length;const digits new Array(m 1).fill(0);for (let i 0; i m; i) {digits[i] parseInt(s[m - 1 - i]);}// digits[m] 已经是 0用于吸收最终进位// dp[carry][aliveA][aliveB]let dp Array.from({ length: 2 }, () Array.from({ length: 2 }, () Array(2).fill(0)));dp[0][1][1] 1;for (let pos 0; pos m; pos) {const ndp Array.from({ length: 2 }, () Array.from({ length: 2 }, () Array(2).fill(0)));const target digits[pos];for (let carry 0; carry 1; carry) {for (let aliveA 0; aliveA 1; aliveA) {for (let aliveB 0; aliveB 1; aliveB) {const ways dp[carry][aliveA][aliveB];if (ways 0) continue;// 构造 a 当前位可选的数字及对应的下一 alive 状态let aChoices;if (aliveA 1) {aChoices [];for (let d 1; d 9; d) {aChoices.push([d, 1]);}if (pos 0) {aChoices.push([0, 0]); // 选 0 表示 a 在此位结束}} else {aChoices [[0, 0]];}// 构造 b 当前位可选的数字及对应的下一 alive 状态let bChoices;if (aliveB 1) {bChoices [];for (let d 1; d 9; d) {bChoices.push([d, 1]);}if (pos 0) {bChoices.push([0, 0]); // 选 0 表示 b 在此位结束}} else {bChoices [[0, 0]];}for (const [da, na] of aChoices) {for (const [db, nb] of bChoices) {const sum da db carry;if (sum % 10 ! target) continue;const ncarry Math.floor(sum / 10);ndp[ncarry][na][nb] ways;}}}}}dp ndp;}// 最终要求无剩余进位a 和 b 都已经结束return 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 位。