[HOJ] 40 - Money Systems

Problem : 40 - Money Systems

Problem：

你有看過龍使嗎？那是一部充滿歡笑的童話故事。

傳說，卡恩國的新國王為了紀念他與奧黛麗雅的日子，決定在卡恩國發起一套新的貨幣系統！因此他下令要某条幫他設計一套新的貨幣系統，某条好威，發明了一系列的貨幣，而他覺得這樣也太過於簡單，於是決定跟自己玩一個遊戲，他想研究說對於一個錢數，有多少種表示方法。

假設貨幣系統裡有{1, 2, 5, 10 ... }，而你要湊出18元，你有18*1, 9*2, 8*2+2, 3*5+2+1 ... 許多種方法。

現在某条都把答案算出來了，他需要一個人跟他確認答案正不正確，請你幫他算出答案後告訴他有多威能吧！

Input：

貨幣有V種(1 <= V <= 25)，所要構造的錢數為N(1 <= N <= 10000)。
第一行有兩個數字V N。 第二行有V個數字，代表的是貨幣的面額。

Output：

輸出你覺得是答案的答案。
保證答案不超過long long範圍。

Sample Input：

3 10
1 2 5

--------------------------------------------------------------------------------------------------------
#include<stdio.h>
long long int s[10005]={0};
int d[30];
int main(){
    int n,m,i,j;
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++)
        scanf("%d",&d[i]);
    s[0]=1;
    for(i=0;i<n;i++)
        for(j=d[i];j<=m;j++)
            s[j]+=s[j-d[i]];
    printf("%lld\n",s[m]);
}