题目地址:Ural 1353

定义dp[i][j]。表示当前位数为i位时，各位数和为j的个数。

对于第i位数来说。总能够看成在前i-1位后面加上一个0~9。所以状态转移方程就非常easy出来了:

dp[i][j]=dp[i][j]+dp[i][j-1]+dp[i][j-2]+.......+dp[i][j-9]；

最后统计就可以。

代码例如以下：

#include <iostream>

#include <cstdio>

#include <string>

#include <cstring>

#include <stdlib.h>

#include <math.h>

#include <ctype.h>

#include <queue>

#include <map>

#include <set>

#include <algorithm>

using namespace std;

const int INF=0x3f3f3f3f;

#define LL long long

int dp[10][90];

int main()

{

    int n, i, j, sum, s, k;

    memset(dp,0,sizeof(dp));

    for(i=1;i<=9;i++)

        dp[1][i]=1;

    for(i=2;i<=9;i++)

    {

        s=0;

        for(j=1;j<=81;j++)

        {

            for(k=0;k<j&&k<=9;k++)

            {

                dp[i][j]+=dp[i-1][j-k];

            }

        }

    }

    while(scanf("%d",&n)!=EOF)

    {

        if(n==1)

        {

            puts("10");

            continue ;

        }

        sum=0;

        for(i=1;i<=9;i++)

        {

            sum+=dp[i][n];

        }

        printf("%d\n",sum);

    }

    return 0;

}