数位DP

题意

给你一个数 ，问你符合以下条件的有序对 有几个：
1、 其中 代表 在十进制下的数位和
2、

思路

数位DP基本操作：
1、先写一个按数位的暴力 DFS (不要使用全局状态变量)

// pos: 当前要处理的位
// digitA: A数字当前位的取值范围 [0, digitA]
// digitB: B数字当前位的取值范围 [0, digitB]
// limitA: A数字的取值范围是否被限制 (数位DP常见思想)
// limitB: B数字的取值范围是否被限制 (数位DP常见思想)
// delta: S(A) - S(B) 

int dfs(int pos = 0, int delta = 0, bool limitA = true, bool limitB = true) {
    if (pos == s.size()) return delta > 0;
    // 保证 0 <= A <= N
    int digitA = limitA ? s[pos] - '0' : 9, ans = 0;
    // 暴力 DFS A, B 每一位的情况
    for (int i = 0; i <= digitA; ++i) {
        // 保证 0 <= B <= A <= N
        int digitB = limitB ? i : 9;
        for (int j = 0; j <= digitB; ++j)
            ans = (ans + dfs(pos + 1, delta + j - i, limitA && i == digitA, limitB && j == digitB)) % MOD;
    }
    return ans;
}

2、然后直接记忆化（注意 delta 可能会小于 0）

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7, N = 105, M = 2e3 + 5;
const int offset = 900;

string s;
int dp[N][M][2][2];

int dfs(int pos = 0, int delta = offset, bool limitA = true, bool limitB = true) {
    if (pos == s.size()) return delta > offset;
    if (~dp[pos][delta][limitA][limitB]) return dp[pos][delta][limitA][limitB];
    int digitA = limitA ? s[pos] - '0' : 9, ans = 0;
    for (int i = 0; i <= digitA; ++i) {
        int digitB = limitB ? i : 9;
        for (int j = 0; j <= digitB; ++j)
            ans = (ans + dfs(pos + 1, delta + j - i, limitA && i == digitA, limitB && j == digitB)) % MOD;
    }
    return dp[pos][delta][limitA][limitB] = ans;
}

int main() {
    memset(dp, -1, sizeof(dp));
    cin >> s;
    cout << dfs() << endl;
}