学步园

在不大于1000000000的数里，各个数位上的数字之和为s的数有多少个。

很容易想到通过背包来做，但是如果只是简单按数位递推，如何排除0112和112这种重复的情况呢？

处理的办法是不把0作为物品，但位数i不仅仅从i-1递推，而是从0到i-1都要统计进来。

#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <math.h>
using namespace std;

int dp[10][82];

void init()
{
    memset(dp, 0, sizeof(dp));
    for(int k = 0; k < 10; k++) dp[k][0] = 1;
    for(int i = 0; i < 10; i++) dp[1][i] = 1;
    for(int k = 2; k < 10; k++)
        for(int t = 0; t < k; t++)
            for(int i = 1; i < 10; i++)
                for(int j = i; j < 82; j++)
                    dp[k][j] += dp[t][j - i];
}
int s;

int main()
{
//    freopen("10444.in", "r", stdin);

    init();
    while(scanf("%d", &s), s)
    {
        int ans = dp[9][s];
        if(s == 1) ans++;
        printf("%d\n", ans);
    }
    return 0;
}