动态规划（6）——VF（NYOJ269）*

英文题目，比较难懂。大概意思：就是求1到10^9里的数满足每位相加之和等于s的数的个数。

比如1到10^9中的数满足每位相加起来都是1的有10个：1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000；

AC代码如下：

       看别人的，还不是太懂，先记下来，慢慢琢磨吧。

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
using namespace std;
int dp[10][82];
int main()
{
    int n;
    memset(dp,0,sizeof(dp));
    for(int i=1;i<10;i++)
    {
        dp[1][i]=1;//1位数中每位相加为1……10的都是1个。
    }
    for(int i=1;i<10;i++)//数的位数，从位数为1到位数为9
    {
        for(int j=1;j<=i*9;j++)//某个数的各个位数相加之和为j,最大为9*9=81
        {
            for(int k=0;k<=9&&k<=j;k++)//?
            {
                dp[i][j]+=dp[i-1][j-k];//?
            }
        }
    }
    while(scanf("%d",&n)!=EOF)
    {
        int ans=0;
        if(n==1)//如和就是1,则就输出10就ok
        {
            printf("%d
",10);
            continue;
        }
        else
        {
            for(int i=1;i<10;i++)//不然将和为n的1到9位数的个数全都加起来
            {
                ans+=dp[i][n];
            }
            printf("%d
",ans);
        }
    }
    return 0;
}