题目传送门
/*
题意:1~1e9的数字里,各个位数数字相加和为s的个数
递推DP:dp[i][j] 表示i位数字,当前数字和为j的个数
状态转移方程:dp[i][j] += dp[i-1][j-k],为了不出现负数
改为:dp[i][j+k] += dp[i-1][j]
*/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
using namespace std;
const int MAXN = 1e4 + ;
const int INF = 0x3f3f3f3f;
int dp[][];
int main(void) //URAL 1353 Milliard Vasya's Function
{
//freopen ("F.in", "r", stdin);
int s;
while (scanf ("%d", &s) == )
{
memset (dp, , sizeof (dp));
dp[][] = ;
for (int i=; i<=; ++i)
{
for (int j=; j<=s; ++j)
{
if (dp[i-][j])
{
for (int k=; k<=; ++k) dp[i][j+k] += dp[i-][j];
}
}
}
if (s == ) dp[][s] += ;
printf ("%d\n", dp[][s]);
}
return ;
}