The cows have not only created their own government but they have chosen to create their own money system. In their own rebellious way, they are curious about values of coinage. Traditionally, coins come in values like 1, 5, 10, 20 or 25, 50, and 100 units, sometimes with a 2 unit coin thrown in for good measure.

The cows want to know how many different ways it is possible to dispense a certain amount of money using various coin systems. For instance, using a system of {1, 2, 5, 10, ...} it is possible to create 18 units several different ways, including: 18x1, 9x2, 8x2+2x1, 3x5+2+1, and many others.

Write a program to compute how many ways to construct a given amount of money using supplied coinage. It is guaranteed that the total will fit into both a signed long long (C/C++) and Int64 (Free Pascal).

PROGRAM NAME: money

INPUT FORMAT

The number of coins in the system is V (1 <= V <= 25).

The amount money to construct is N (1 <= N <= 10,000).

Line 1:	Two integers, V and N
Lines 2..:	V integers that represent the available coins (no particular number of integers per line)

SAMPLE INPUT (file money.in)

3 10
1 2 5

OUTPUT FORMAT

SAMPLE OUTPUT (file money.out)

10

題意：
給出v中硬幣面值和總價錢N。計算能有多少種方法使得利用v中若干硬幣組成N。

代碼如下：

/*
LANG: C
TASK: money
*/
#include<stdio.h>
long long dp[26][10001];
int main()
{
    freopen("money.in", "r", stdin);
    freopen("money.out", "w", stdout);
    int i, j, n, m, s[26];
    scanf("%d%d", &n, &m);
    for (i = 1; i <= n; i++)
    {
        scanf("%d", &s[i]);
    }
    for (i = 1; i <= n; i++)
    {
        dp[i][0] = 1;//取0元是可以的。 
    }
    for (i = 1; i <= n; i++)//[i, j]表示在前i種硬幣種能組成j元的情況個數 
    {
        for (j = 1; j <= m; j++)
        {
            if (j - s[i] >= 0)
            {
                dp[i][j] = dp[i-1][j] + dp[i][j-s[i]];
            }
            else
            {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    printf("%lld\n", dp[n][m]);
    fclose(stdin);
    fclose(stdout);
    //system("pause");
    return 0;
}


由于每次計算dp[i][j] 都是利用到dp[i-1][j]和d[i][j-s[i]].而計算順序是從左到右，從上到下。所以每次計算dp[i][j]時，兩個前提條件都已被計算。
所以可以只用一維空間。
代碼如下：

/*
LANG: C
TASK: money
*/
#include<stdio.h>
long long dp[10001];
int main()
{
    freopen("money.in", "r", stdin);
    freopen("money.out", "w", stdout);
    int i, j, n, m, s[26];
    scanf("%d%d", &n, &m);
    for (i = 1; i <= n; i++)
    {
        scanf("%d", &s[i]);
    }
    dp[0] = 1;
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= m; j++)
        {
            if (j - s[i] >= 0)
            {
                dp[j] = dp[j] + dp[j-s[i]];
            }
        }
    }
    printf("%lld\n", dp[m]);
    fclose(stdin);
    fclose(stdout);
    //system("pause");
    return 0;
}