DP - Counting 计数

http://luoshaochuan.com/2017/07/14/动态规划总结(五）/

划分数

有N个无区别的物品，将它们划为不超过M堆，求划分方案数。

分析

dp[i][j]表示j个物品划为i+1堆,a1,a2,…,ai,则若存在ai=0,则共有dp[i-1][j]堆，若任意ai！=0，共有dp[i][j-i]堆。所以：

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

2.多重集合数

有N种物品，每种物品有Ai个，从这些物品中取出M个，求方案数。

分析

dp[i+1][j]表示前i种物品中取出j个的方案数。则对于第i种物品，可以取出0,1,…Ai个。所以

1	dp[i+1][j]=dp[i][j]+dp[i][j-1]+...+dp[i][j-Ai]=\sum_{k=0}^{min(j,Ai)}dp[i][j-k]

优化

这种求和的动态规划，通常可以把递推式进行变形，从而降低复杂度。

1	\sum_{k=0}^{min(j,Ai)}dp[i]=\sum_{k=0}^{min(j-1,Ai)}dp[i][(j-1)-k]+dp[i][j]-dp[i][j-1-Ai]=dp[i+1][j-1]+dp[i][j]-dp[i]

https://blog.csdn.net/kangyan__/article/details/66969328

描述：计算从1到n中，每个数字（0到9）出现的次数

其中sum[j]和dp[i]表示：数字i中 j 的个数；比如sum[1]和dp[5]就可以表示：5中1的个数为0；sum[1]和dp[11]就可以表示：11中1的个数为2；

int dp[100001];

int main()

{

    int n,sum[10];

    while(~scanf("%d",&n))

    {

        memset(sum,0,sizeof(sum));

        int j=0;

        while(j<10)

        {

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

            dp[j] = 1;

            for (int i = 1; i <= n; i++)

            {

                dp[i] = dp[i%10];

                if(i/10)

                    dp[i] += dp[i/10];

                sum[j] += dp[i];

            }

            j++;

        }

        for(int i=0;i<10;i++)

            printf("%d:%d\n",i,sum[i]);

    }

    return 0;

}