用C++写一个数位DP的模板

以下是一个简单的数位DP模板，使用C语言编写：

#include <stdio.h>
#include <string.h>

#define MAXN 100005
#define MAXM 10

int dp[MAXN][MAXM];

int solve(int n, int m) {
if (n == 0) return 1;
if (dp[n][m] != -1) return dp[n][m];
int res = 0;
for (int i = 0; i <= m; i++) {
res += solve(n - 1, i);
}
dp[n][m] = res;
return res;
}

int main() {
memset(dp, -1, sizeof(dp));
int n;
scanf("%d", &n);
int ans = 0;
for (int i = 1; i <= 9; i++) {
ans += solve(n - 1, i);
}
printf("%d\n", ans);
return 0;
}

这个模板可以用来解决一些数位DP问题，例如计算1到n中所有数位上的数字之和为k的数的个数。

相关问题

用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 这个子串。具体可以看注释。