2026-07-17统计满足数位和数组的非递减数组数目。用go语言给定一个长度为 n 的整数数组 digitSum。需要统计能构造出多少个长度为 n 的数组 arr同时满足arr 的每一项都是 0 到 5000 之间的整数。arr 是非递减的即 arr[0] ≤ arr[1] ≤ … ≤ arr[n-1]。对于每个位置 iarr[i] 的十进制各位数字之和必须等于 digitSum[i]。最终返回不同有效数组的个数结果对 10⁹ 7 取模。1 digitSum.length 1000。0 digitSum[i] 50。输入 digitSum [25,1]。输出 6。解释数位和为 25 的数字有 799、889、898、979、988 和 997。数位和为 1 且可以出现在这些值之后同时保持数组非递减的唯一数字是 1000。因此有效数组为 [799, 1000]、[889, 1000]、[898, 1000]、[979, 1000]、[988, 1000] 和 [997, 1000]。因此答案是 6。题目来自力扣3883。1. 预处理按数位和分组数字枚举从0到5000的每一个整数x利用递推公式digSum[x] digSum[x/10] (x % 10)快速算出它的十进制各位数字之和。最大数位和出现在4999其值为4999 31。因此所有数字被分到32个桶中每个桶对应一个数位和031。最终得到sumToNums数组其中sumToNums[s]存放所有数位和为s的数字并且由于枚举顺序是从小到大每个桶内的数字天然保持升序。这部分计算只执行一次与输入无关。2. 动态规划准备创建一个长度为5001的数组ff[x]表示以数字x结尾的有效非递减数组的数量。为了统一处理第一个元素设置一个虚拟起点令f[0] 1相当于认为在前一个位置存在一个数位和为0的数字0它小于等于任何有效数字。这样在计算第一个位置时可以无缝复用后续的转移逻辑。变量pre记录前一个位置的数位和初始设为0。3. 逐位计算有效数组数量对输入序列digitSum中的每个目标数位和cur依次处理3.1 可行性检查如果cur 31说明要求的数位和不可能由05000内的数字实现直接返回0。3.2 获取相关数字列表a sumToNums[pre]前一个位置允许的所有数字已按升序排列。当前列表b sumToNums[cur]当前位置允许的所有数字同样升序。3.3 双指针累加转移初始化指针j 0指向a的开头累加和sum 0。遍历当前列表b中的每一个候选数字x因为a和b都已升序我们可以利用双指针技巧不断右移j将a中所有满足a[j] x的f[a[j]]累加到sum中。这样保证了非递减约束——前一个数字只要小于等于x就能接上。当所有符合条件的a[j]都处理完后sum就代表了所有以x结尾的当前序列的个数。将它对10^97取模后赋给f[x]。处理完当前列表后f数组就更新为以各个x数位和为cur结尾的有效序列数量。3.4 进入下一轮令pre cur为下一个位置的转移做好准备。4. 汇总最终答案遍历完所有位置后pre中存储的是最后一个目标数位和。将所有数位和为pre的数字x对应的f[x]累加起来就得到了整个序列的不同有效数组总数。最后再取一次模返回结果。复杂度分析时间复杂度预处理部分只需遍历5001个数字复杂度O(5000)。动态规划部分对每个digitSum元素我们遍历了前一个数位和的数字列表和当前数位和的数字列表。尽管有双重循环但双指针的内层while在每个状态转移中总共只将前一个列表扫描一遍。因此总操作次数等于相邻两步列表长度之和的总和。所有桶的数字总数不超过5001假设digitSum长度为n最大1000总时间复杂度为O(5000 n * L_max)其中L_max是单个数位和的最大数字个数远小于5000。实际运行极其迅速。额外空间复杂度全局的sumToNums保存了所有数字的分组占用O(5000)空间动态规划数组f同样占用O(5000)空间。除输入外总额外空间为O(5000)即常数级非常节省。Go完整代码如下packagemainimport(fmt)constmx5001constmaxDigitSum31// 4999 的数位和最大varsumToNums[maxDigitSum1][]intfuncinit(){digSum:[mx]int{}forx:rangedigSum{// 去掉 x 的个位问题变成 x/10 的数位和即 digSum[x/10]digSum[x]digSum[x/10]x%10sumToNums[digSum[x]]append(sumToNums[digSum[x]],x)}}funccountArrays(digitSum[]int)(ansint){constmod1_000_000_007f:[mx]int{1}// f[x] 表示以 x 结尾的有效数组的个数pre:0for_,cur:rangedigitSum{ifcurmaxDigitSum{return0}a:sumToNums[pre]j,m:0,len(a)sum:0for_,x:rangesumToNums[cur]{// 有效数组的前一个数只要 x 就行for;jma[j]x;j{sumf[a[j]]}// sum 现在就是以 x 结尾的有效数组的个数f[x]sum%mod}precur// 记录上一个数位和}for_,x:rangesumToNums[pre]{ansf[x]}returnans%mod}funcmain(){digitSum:[]int{25,1}result:countArrays(digitSum)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-fromtypingimportList MOD1_000_000_007MX5001MAX_DIGIT_SUM31# 4999 的数位和最大为 31# 预计算按数位和分组数字 0..5000sum_to_nums[[]for_inrange(MAX_DIGIT_SUM1)]dig_sum[0]*MXforxinrange(MX):dig_sum[x]dig_sum[x//10](x%10)sum_to_nums[dig_sum[x]].append(x)defcountArrays(digitSum:List[int])-int:f[0]*MX f[0]1# 以 0 结尾的方案数为 1虚起点pre0# 上一个数位和初始为 0forcurindigitSum:ifcurMAX_DIGIT_SUM:return0asum_to_nums[pre]# 前一个数位和对应的数字列表j0mlen(a)s0forxinsum_to_nums[cur]:# 累加所有满足 a[j] x 的 f[a[j]]whilejmanda[j]x:sf[a[j]]j1f[x]s%MOD precur# 更新前一个数位和ans0forxinsum_to_nums[pre]:ansf[x]returnans%MOD# 示例测试if__name____main__:digitSum[25,1]print(countArrays(digitSum))C完整代码如下#includeiostream#includevectorusingnamespacestd;constintMX5001;constintMAX_DIGIT_SUM31;// 4999 的数位和最大为 31constintMOD1000000007;// 预计算按数位和分组数字 0..5000只初始化一次constvectorvectorintgetSumToNums(){staticvectorvectorintsumToNums[](){vectorvectorintres(MAX_DIGIT_SUM1);vectorintdigSum(MX,0);for(intx0;xMX;x){if(x0)digSum[x]digSum[x/10](x%10);res[digSum[x]].push_back(x);}returnres;}();returnsumToNums;}intcountArrays(constvectorintdigitSum){constautosumToNumsgetSumToNums();vectorintf(MX,0);f[0]1;// 以 0 结尾的方案数为 1虚起点intpre0;// 上一个数位和初始为 0for(intcur:digitSum){if(curMAX_DIGIT_SUM)return0;constautoasumToNums[pre];intj0,ma.size();longlongsum0;// 用 64 位避免溢出for(intx:sumToNums[cur]){// 累加所有满足 a[j] x 的 f[a[j]]while(jma[j]x){sumf[a[j]];j;}f[x]sum%MOD;}precur;}longlongans0;for(intx:sumToNums[pre]){ansf[x];}returnans%MOD;}intmain(){vectorintdigitSum{25,1};coutcountArrays(digitSum)endl;return0;}