根据之前搜索到的题目描述和解题思路我直接为你编写 Go 实现。LeetCode 3883 - Count Non Decreasing Arrays With Given Digit Sums (Go)解题思路1. 预处理枚举 [0, 5000] 中每个数字按其数位和分组2. 动态规划 前缀和优化dp[j] 表示前一个位置选择第 j 个候选数字的方案数用前缀和加速非递减约束的转移gopackage mainimport (sort)const MOD 1_000_000_007func countArrays(digitSum []int) int {n : len(digitSum)// 预处理按数位和分组收集 [0, 5000] 中的数字// digitSum[i] 50所以只需要 0~50 的分组candidates : make([][]int, 51)for num : 0; num 5000; num {s : digitSumOf(num)if s 50 {candidates[s] append(candidates[s], num)}}// 如果某个位置没有候选数字直接返回 0for _, s : range digitSum {if len(candidates[s]) 0 {return 0}}// 确保每个分组都是有序的由于按 num 顺序添加已经有序for i : range candidates {sort.Ints(candidates[i])}// 初始化第一个位置每个候选数字都是一种方案first : candidates[digitSum[0]]dp : make([]int, len(first))for i : range dp {dp[i] 1}// 处理后续每个位置for i : 1; i n; i {prev : candidates[digitSum[i-1]]curr : candidates[digitSum[i]]// 计算 dp 的前缀和prefix : make([]int, len(prev))prefix[0] dp[0]for j : 1; j len(prev); j {prefix[j] (prefix[j-1] dp[j]) % MOD}newDp : make([]int, len(curr))// 双指针对于当前每个候选找到所有 它的 prev 候选p : 0for j : 0; j len(curr); j {currVal : curr[j]for p len(prev) prev[p] currVal {p}// prev[0..p-1] 都 currValif p 0 {newDp[j] prefix[p-1]}}dp newDp}// 统计所有方案ans : 0for _, v : range dp {ans (ans v) % MOD}return ans}// 计算数字的数位和func digitSumOf(num int) int {sum : 0for num 0 {sum num % 10num / 10}return sum}关键点说明要点 说明预处理 枚举 0~5000按数位和 0~50 分组每组最多约 100 个数字双指针优化 两个候选列表都是有序的用双指针在 O(\|prev\| \|curr\|) 内完成转移前缀和 prefix[j] 表示 dp[0..j] 的和快速求所有合法前驱的方案数之和空间优化 只保留一维 DP空间复杂度 O(m)m 为候选数字数量复杂度- 时间O(n × m)n ≤ 1000m 为每组候选数数量- 空间O(m)示例验证- digitSum [25, 1] → 输出 6799/889/898/979/988/997 后面接 1000- digitSum [1] → 输出 41, 10, 100, 1000- digitSum [2, 49, 23] → 输出 049 在 [0,5000] 内无数位和为 49 的数字