洛谷P4999题解：烦人的数学作业 - 数位DP算法深度剖析

题目分析

题目要求计算区间[L,R]内所有整数的数字和，例如123的数字和为1+2+3=6。这是一个典型的数位动态规划问题，需要处理大数范围和数字分解。

算法核心思路

1. 将问题转化为[0,R]的和减去[0,L-1]的和

2. 使用数位DP记忆化搜索方法

3. 状态设计：

• pos: 当前处理的位置

• sum: 当前数字和

• limit: 是否受到上界限制

完整C++代码实现

#include <iostream>
#include <cstring>
using namespACe std;

const int MOD = 1e9+7;
typedef long long ll;
ll dp[20][200]; // dp[pos][sum]
int digit[20];

ll dfs(int pos, int sum, bool limit) {
    if(pos == 0) return sum; // 递归终点返回数字和
    if(!limit && dp[pos][sum] != -1) 
        return dp[pos][sum]; // 记忆化返回
    
    int up = limit ? digit[pos] : 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;
}

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;
}

代码解析

1. solve函数：处理输入数字，分解各位数字

2. dfs函数：核心递归函数，处理数位计算

3. 记忆化优化：避免重复计算提升效率

4. 取模处理：结果对1e9+7取模

算法复杂度分析

• 时间复杂度：O(logN) 每个数位处理一次

• 空间复杂度：O(logN) 存储数位和DP状态