题目大意：
给出n，问从0到n有多少数对(A,B)，满足A<B,但是A的数位之和大于B的数位之和？
解题思路：
数位dp。之前使用数位dp，都是求解一个范围[L,R]内满足某个条件的数有多少。这次是求满足条件的对数。
学到的第一个是用空间换时间，就是把lima，limb之类的都写进dp里，形成一个5维dp
dp[pos][sum][lima][limb][limit]
分别代表：
1.当前搜索到的位置
2.前面已经搜索出来的各位之差
3.第一个数最高位此时是否有限制
4.第二个数最高位此时是否有限制
5.第二个数在前面是否已经大于了第一个数
普通的数位dp是在dfs的时候构造一个满足条件的数，而这里的数位dp在dfs的时候通过枚举位置同时构造了两个数A,B，并且在其中维护A<B。于是dfs就同时枚举两个数在pos位置的数字。最后dfs出去的条件是sum是否大于基数，如果大于基数代表A的数位之和大于B的数位之和。那么就得到一组满足条件的(A,B)。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int base = 1000;

string str;

ll dp[110][2005][2][2][2];
/*1.当前搜索到的位置
2.前面已经搜索出来的各位之差 
3.第一个数最高位此时是否有限制
4.第二个数最高位此时是否有限制
5.第二个数在前面是否已经大于了第一个数 */
ll dfs(int pos,int sum ,bool lima, bool limb, bool limit)
{
    if(pos < 0) {
        return sum > base;    
    }
    if(dp[pos][sum][lima][limb][limit] != -1) return dp[pos][sum][lima][limb][limit];
    int up1 = lima ? str[pos] - '0' : 9;
    int up2 = limb ? str[pos] - '0' : 9;
    ll ans = 0;
    for(int i = 0; i <= up1; i++) {
        for(int j = 0; j <= up2; j++) {
            if(i > j && !limit)
                continue;
            ans += dfs(pos-1,sum+i-j ,lima && (i==up1), limb &&(j==up2), limit||(j>i));
            ans %= mod; 
        }
    }
    return dp[pos][sum][lima][limb][limit] = ans;
}

int main()
{
    memset(dp, -1, sizeof(dp));
    cin >> str;
    int len = str.length();
    int L = 0, R = len-1;
    while(L < R)
    {
        swap(str[L++],str[R--]);
    }

    cout << dfs(len - 1,base ,1, 1, 0) << endl;
}