用c++写一个数位dp的模板

好的，以下是一个简单的数位dp模板：

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

const int MAXN = 15;

int dp[MAXN][MAXN][2]; // dp[i][j][0/1]表示当前处理到第i位，前一位为j，是否达到上限的方案数

int dfs(int pos, int pre, int limit, int num[]) {
    if (pos == 0) return 1; // 递归边界，处理完所有位
    if (!limit && dp[pos][pre][limit] != -1) return dp[pos][pre][limit]; // 记忆化
    int up = limit ? num[pos] : 9;
    int res = 0;
    for (int i = 0; i <= up; i++) {
        if (pre == 6 && i == 2) continue; // 不包含 62
        res += dfs(pos - 1, i, limit && i == up, num);
    }
    if (!limit) dp[pos][pre][limit] = res; // 记忆化
    return res;
}

int solve(int n) {
    int len = 0, num[MAXN];
    memset(dp, -1, sizeof(dp));
    while (n) {
        num[++len] = n % 10;
        n /= 10;
    }
    return dfs(len, 0, 1, num);
}

int main() {
    int n;
    cin >> n;
    cout << solve(n) << endl;
    return 0;
}

这个模板可以求解类似于求解一个数的各个数位上的数字之和的问题。具体做法是使用记忆化搜索，从高到低枚举每一位上的数字，如果当前位是6，那么下一位不能是2，否则就会出现 62 这个子串。具体可以看注释。