用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的数的个数。