洛谷P4999题解析：动态规划求解数字拆分与求和问题（附代码）
2天前
一、题目解读
洛谷P4999题要求处理给定区间 [L, R] 内数字的拆分与求和问题。每个数字需拆分为其各位数字之和，并计算区间内所有数字之和的累加结果。题目需考虑大数情况，并采用取模运算（MOD=1e9+7）防止溢出。
二、解题思路
核心思路为动态规划 + 记忆化搜索。通过将数字拆分为位数与各位数字之和的状态，利用递归计算不同位数的数字和，并通过记忆化存储避免重复计算。关键在于设计状态转移方程，处理前缀区间和的累加。
三、解题步骤
1. 预处理数字位数：将输入的大数 L 和 R 逆序存储为 digit 数组，记录每位数字。
2. 定义状态 dp[pos][sum]：表示处理到第 pos 位、当前数字和为 sum 时的方案数。
3. 递归计算与记忆化：
递归终点为 pos=0，直接返回 sum。
若当前位未受限（非最高位），且已存在记忆化结果，直接返回。
枚举 0~up（最高位为 digit[pos]，其余位为 9）的每位数字，递归计算下一位，累加结果并取模。
更新记忆化数组。
4. 区间求和：通过 solve(R) - solve(L-1) 计算答案，并处理负数情况（+MOD 后再取模）。
四、代码及注释
#include <iostream>
#include <cstring>
using namespace std;
const int MOD = 1e9+7; // 取模常量
typedef long long ll; // 定义长整型
ll dp[20][200]; // dp[pos][sum]：处理到第pos位、数字和为sum的方案数
int digit[20]; // 存储数字的逆序位数
// 记忆化搜索函数
ll dfs(int pos, int sum, bool limit) {
if(pos == 0) return sum; // 递归终点：当前位为0，返回数字和
if(!limit && dp[pos][sum]!= -1) // 非最高位且已记忆化，直接返回
return dp[pos][sum];
int up = limit? digit[pos] : 9; // 最高位限制为当前位数，其余位可到9
ll res = 0;
for(int i = 0; i <= up; ++i) { // 枚举当前位数字
// 递归计算下一位，累加结果并取模
res = (res + dfs(pos-1, sum+i, limit && i==up)) % MOD;
}
if(!limit) dp[pos][sum] = res; // 非最高位时记忆化存储
return res;
}
// 主计算函数：将数字拆解为位数，调用dfs
ll solve(ll x) {
memset(dp, -1, sizeof dp); // 初始化记忆化数组
int len = 0;
while(x) { // 逆序存储数字位数
digit[++len] = x % 10;
x /= 10;
}
return dfs(len, 0, true); // 从最高位开始，限制位数
}
int main() {
int T;
cin >> T; // 输入测试组数
while(T--) {
ll L, R;
cin >> L >> R; // 输入区间
// 计算区间和，处理负数情况
cout << (solve(R) - solve(L-1) + MOD) % MOD << endl;
}
return 0;
}五、总结
本解法通过动态规划将数字拆分问题转化为状态转移，结合记忆化搜索优化递归效率，有效解决大区间求和问题。时间复杂度为 O(位数×数字和范围)，空间复杂度为 O(位数×数字和范围)。在实际应用中，记忆化搜索可显著提升重复计算场景的性能，是算法优化的关键技巧。
参考：动态规划
原创内容 转载请注明出处
