递推DP URAL 1353 Milliard Vasya's Function

 1 /*
 2     题意：1~1e9的数字里，各个位数数字相加和为s的个数
 3     递推DP：dp[i][j] 表示i位数字，当前数字和为j的个数
 4             状态转移方程：dp[i][j] += dp[i-1][j-k]，为了不出现负数
 5                 改为：dp[i][j+k] += dp[i-1][j]
 6 */
 7 #include <cstdio>
 8 #include <cstring>
 9 #include <cmath>
10 #include <algorithm>
11 #include <string>
12 using namespace std;
13 
14 const int MAXN = 1e4 + 10;
15 const int INF = 0x3f3f3f3f;
16 int dp[10][90];
17 
18 int main(void)        //URAL 1353 Milliard Vasya‘s Function
19 {
20     //freopen ("F.in", "r", stdin);
21 
22     int s;
23     while (scanf ("%d", &s) == 1)
24     {
25         memset (dp, 0, sizeof (dp));
26 
27         dp[0][0] = 1;
28         for (int i=1; i<=9; ++i)
29         {
30             for (int j=0; j<=s; ++j)
31             {
32                 if (dp[i-1][j])
33                 {
34                     for (int k=0; k<=9; ++k)    dp[i][j+k] += dp[i-1][j];
35                 }
36                 
37             }
38         }
39 
40         if (s == 1)    dp[9][s] += 1;
41         printf ("%d\n", dp[9][s]);
42     }
43 
44     return 0;
45 }