7-16 货币系统Ⅰ

7-16 货币系统Ⅰ

给你一个n种面值的货币系统，求组成面值为m的货币有多少种方案。

输入格式
第一行，包含两个整数n和m。

接下来n行，每行包含一个整数，表示一种货币的面值。

输出格式
共一行，包含一个整数，表示方案数。

数据范围
n≤15,m≤3000

输入样例：

3 10
1
2
5

输出样例：

10

代码：

#include<stdio.h>
int n,m;
int a[20];
int sum=0;
int vis[20][100000];
int find(int x,int money)
{
    
    if(money==m)
    {
    
        sum++;
        return 0;
    }
    if(money>m)
        return 0;
    if(x>=n)
        return 0;
    if(vis[x][money]!=0)
        return vis[x][money];
    int len=(m-money)/a[x];
    for(int i=len;i>=0;i--)
        vis[x][money]=find(x+1,money+a[x]*i)+a[x]*i;
}
int main()
{
    
    while( scanf("%d%d",&n,&m)!=EOF)
    {
    
        memset(a,0,sizeof(a));
        memset(vis,0,sizeof(vis));
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    find(0,0);
    printf("%d\n",sum);
        sum=0;
    }
}

202206260906日