洛谷P4999题解析：动态规划求解数字拆分与求和问题（附代码）

一、题目解读

洛谷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(位数×数字和范围)。在实际应用中，记忆化搜索可显著提升重复计算场景的性能，是算法优化的关键技巧。

参考：动态规划