以下是 LeetCode 3883 的 Python3 实现解题思路1. 预处理枚举 0..5000 所有数字按数位和分组。最大数位和为 499931数字4999所以最多32个组。2. 动态规划f[x] 表示以数字 x 结尾的有效非递减数组数量。设虚拟起点 f[0] 1前一个数位和为0数字为0。3. 双指针转移对于当前数位和 cur遍历该组所有数字 x。用双指针在上一组数位和 pre中累加所有 x 的 f 值即为以 x 结尾的方案数。4. 取模结果对 10^9 7 取模。pythonfrom typing import ListMOD 1_000_000_007MX 5001MAX_DIGIT_SUM 31 # 4999 的数位和最大为 31# 预计算按数位和分组数字 0..5000sum_to_nums [[] for _ in range(MAX_DIGIT_SUM 1)]dig_sum [0] * MXfor x in range(MX):dig_sum[x] dig_sum[x // 10] (x % 10)sum_to_nums[dig_sum[x]].append(x)class Solution:def countArrays(self, digitSum: List[int]) - int:f [0] * MXf[0] 1 # 以 0 结尾的方案数为 1虚起点pre 0 # 上一个数位和初始为 0for cur in digitSum:if cur MAX_DIGIT_SUM:return 0a sum_to_nums[pre] # 前一个数位和对应的数字列表j 0m len(a)s 0for x in sum_to_nums[cur]:# 累加所有满足 a[j] x 的 f[a[j]]while j m and a[j] x:s f[a[j]]j 1f[x] s % MODpre cur # 更新前一个数位和ans 0for x in sum_to_nums[pre]:ans f[x]return ans % MOD复杂度分析- 时间复杂度预处理 O(5000)DP 阶段每步双指针总扫描量不超过两组长度之和总体 O(n × L_max)其中 L_max 是单组最大长度实际很小。- 空间复杂度O(5000)用于 f 数组和预计算的分组。
