【欧拉计划】31. Coin sums

（本题取 $n=200$，$m=8$）

【思路】通过观察不难发现本题考察的是 DP。

如果我们用 $dp_{i,j}$ 表示使用 $j$ 种不同面额凑出 $i$ 分钱的方案个数，那么显然有初始状态：

$$dp_{0,1}=1$$

由于本题数据范围不大，我们可以暴力递推，从而覆盖所有情况。用 $val_i$ 表示第 $i$ 种货币的面额，则有：

$$dp_{i,j}=\sum_{i=1}^n \sum_{j=1}^m \sum_{k=1}^j dp_{i-val_j,k}$$

这样我们便得到了一个 $\mathcal O(nm^2)$ 的做法：

#include<stdio.h>
const int value[]={0,1,2,5,10,20,50,100,200};
int dp[201][10],ans;
int main()
{
    dp[0][1]=1;
    for(int i=1;i<=200;++i)
    {
        for(int j=1;value[j]<=i;++j)
        {
            for(int k=1;k<=j;++k)
            {
                dp[i][j]+=dp[i-value[j]][k];
            }
        }
    }
    for(int i=1;i<10;++i)ans+=dp[200][i];
    printf("%d",ans);
    return 0;
}

【优化】我们可以采用完全背包进行优化。

不妨用 $dp_j$ 表示能够凑出 $j$ 分钱的方案总数，则初始状态为：

$$dp_0=1$$

接着我们使用完全背包的递推方式：

$$dp_j=\sum_{i=1}^m \sum_{j=val_i}^n dp_{j-val_i}$$

这样我们可以将时间复杂度优化到 $\mathcal O(nm)$，空间复杂度优化到 $\mathcal O(n)$：

#include<stdio.h>
const int value[]={0,1,2,5,10,20,50,100,200};
int dp[201],ans;
int main()
{
    dp[0]=1;
    for(int i=1;i<=8;++i)
    {
        for(int j=value[i];j<=200;++j)
        {
            dp[j]+=dp[j-value[i]];
        }
    }
    printf("%d",dp[200]);
    return 0;
}